LeetCode 1929 - Concatenation of Array

LeetCode Problem 1929

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

Problem Understanding

This problem asks us to take an input array nums of length n and produce a new array ans of length 2n where the first half of ans is identical to nums and the second half is also identical to nums. In other words, ans is formed by concatenating nums with itself.

The input nums is a list of integers ranging from 1 to 1000, and the length n can be up to 1000. The output must preserve the exact order of elements in nums and repeat them immediately after the first sequence. This is essentially a simulation problem where we need to construct an array based on a clear pattern.

Key edge cases include when nums has only one element, when all elements are identical, and when the array is at its maximum allowed size. These are important because naive approaches that incorrectly handle indexing or copying may fail in these scenarios. The problem guarantees that nums is non-empty and contains integers within a specific range, which simplifies error handling.

Approaches

A straightforward brute-force approach is to initialize an empty array ans and then append each element of nums twice: first for the original position, then for the repeated position. This approach is correct but involves explicit iteration and manual handling of indices. For the given constraints, this is feasible since n <= 1000, but we can optimize the implementation by leveraging array concatenation or preallocation to avoid dynamic resizing.

The key insight for an optimal solution is recognizing that the concatenation operation is simply repeating nums twice. Most modern programming languages support array concatenation or repetition operations that directly produce the desired output in a single step. This allows us to avoid manual iteration and makes the code cleaner, more readable, and slightly more efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Append each element twice manually
Optimal	O(n)	O(n)	Use built-in array concatenation or repetition

Algorithm Walkthrough

1. Determine the length of the input array nums and store it in a variable n. This step ensures clarity and allows indexing if needed.
2. Initialize an array ans with a size of 2 * n (optional in languages that support direct concatenation). This preallocation can improve performance by avoiding repeated resizing.
3. Concatenate nums with itself. In Python, this can be done with the + operator (nums + nums). In Go, we can use the append function to append nums to itself.
4. Return the resulting array ans.

Why it works: The algorithm works because array concatenation directly duplicates the sequence of elements without altering their order. The invariant is that for every index i < n, ans[i] == nums[i] and ans[i + n] == nums[i], which satisfies the problem statement.

Python Solution

from typing import List

class Solution:
    def getConcatenation(self, nums: List[int]) -> List[int]:
        # Concatenate nums with itself using list addition
        ans = nums + nums
        return ans

In this Python implementation, we leverage Python's list concatenation operator + to duplicate the array. This eliminates the need for manual loops or indexing and directly produces the desired 2n-length array. The returned ans satisfies the problem requirements exactly.

Go Solution

func getConcatenation(nums []int) []int {
    n := len(nums)
    ans := make([]int, 2*n)
    copy(ans[:n], nums)
    copy(ans[n:], nums)
    return ans
}

In Go, we preallocate the slice ans with length 2n using make. Then we use the built-in copy function to first copy nums into the first half and then into the second half of ans. This approach avoids repeated dynamic resizing of slices and handles the array duplication efficiently.

Worked Examples

Example 1: nums = [1,2,1]

Step	Operation	ans
Initial	nums = [1,2,1]	[]
Concatenate	nums + nums	[1,2,1,1,2,1]

Example 2: nums = [1,3,2,1]

Step	Operation	ans
Initial	nums = [1,3,2,1]	[]
Concatenate	nums + nums	[1,3,2,1,1,3,2,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Concatenating or copying an array of length n requires iterating over each element once
Space	O(n)	The output array has length 2n, proportional to n

The time complexity is linear because every element of the original array is read once and written twice. The space complexity is linear because we allocate a new array to hold the doubled elements.

Test Cases

# Provided examples
assert Solution().getConcatenation([1,2,1]) == [1,2,1,1,2,1]  # basic repeat
assert Solution().getConcatenation([1,3,2,1]) == [1,3,2,1,1,3,2,1]  # even-length array

# Boundary cases
assert Solution().getConcatenation([1]) == [1,1]  # single element
assert Solution().getConcatenation([1000]*1000) == [1000]*2000  # max length, all identical
assert Solution().getConcatenation(list(range(1, 6))) == [1,2,3,4,5,1,2,3,4,5]  # sequential numbers

# Mixed elements
assert Solution().getConcatenation([5,4,3,2,1]) == [5,4,3,2,1,5,4,3,2,1]  # descending
assert Solution().getConcatenation([1,1,2,2,3,3]) == [1,1,2,2,3,3,1,1,2,2,3,3]  # duplicates

Test	Why
[1,2,1]	Validates basic repetition
[1,3,2,1]	Validates longer arrays
[1]	Edge case with single element
[1000]*1000	Stress test for maximum size
[1,2,3,4,5]	Sequential numbers
[5,4,3,2,1]	Descending order
[1,1,2,2,3,3]	Handling duplicates

Edge Cases

One important edge case is an array of length 1. Here, the algorithm must correctly produce two identical elements in the output. A naive indexing approach could fail if it assumes multiple elements exist.

Another edge case is an array where all elements are the same. This tests whether the function handles repeated values correctly without modifying or skipping elements during concatenation.

A third edge case is the maximum allowed array size, n = 1000. The algorithm must handle large arrays efficiently without exceeding memory or running into performance issues. By using either array concatenation in Python or preallocation with copy in Go, we ensure that even the largest allowed input is processed correctly.