Concatenation of Array

How it works

The problem defines the result array ans such that ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n. Instead of looping through the input twice, we can fill both required positions in the result array simultaneously while iterating through the input array just once. This utilizes the index mapping i and i + n directly.

Steps

1. Determine the length n of the input array.
2. Initialize a result array ans of size 2n.
3. Iterate through the input array nums using an index i from 0 to n - 1.
4. For each element at index i:
   • Set ans[i] = nums[i].
   • Set ans[i + n] = nums[i].
5. Return the resulting array.

Complexity

• Time complexity: O(n) where n is the length of the input array. Although we iterate through the input once, we still perform 2n total writes to the output array.
• Space complexity: O(n) as we must allocate an array of size 2n for the output.

Things to watch for

Incorrect Result Array Size

Allocating an array of size n instead of 2n causes an index out of bounds error when writing to the second half.

Off-by-One When Using Index Offset

When using the one-pass approach with ans[i + n] = nums[i], forgetting that indices are zero-based or miscalculating the offset leads to incorrect placement of elements in the second half.

from typing import List

class Solution:
    def getConcatenation(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * (2 * n)
        for i, num in enumerate(nums):
            ans[i] = ans[i + n] = num
        return ans

class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(2 * n);
        for (int i = 0; i < n; ++i) {
            ans[i] = ans[i + n] = nums[i];
        }
        return ans;
    }
};