Concatenation of Array (LC 1929)

Pattern: Array manipulation / Basic iteration
Difficulty: Easy
Key Concept: Build a result array by repeating the original sequence once in the first half and once in the second half.

Problem Statement

You are given an integer array nums of length n. Create an array ans of length 2n such that:

• For every index i with 0 <= i < n: ans[i] == nums[i]
• For every index i with 0 <= i < n: ans[i + n] == nums[i]

Return ans.

Input: Integer array nums of length n (e.g. nums = [1, 2, 1]).
Output: Integer array of length 2n that is nums concatenated with itself.

---

1. Algorithm & Pseudocode

Goal: Fill ans so the first n slots and the last n slots both equal nums.

Brute force (two loops)

1. Allocate ans of size 2 * n.
2. First loop: for i from 0 to n - 1, set ans[i] = nums[i].
3. Second loop: for i from 0 to n - 1, set ans[i + n] = nums[i].
4. Return ans.

Optimal (single loop)

1. Allocate ans of size 2 * n.
2. For i from 0 to n - 1:
   • ans[i] = nums[i]
   • ans[i + n] = nums[i]
3. Return ans.

Alternative optimal (bulk copy)

1. Allocate ans of size 2 * n.
2. Copy nums into ans starting at index 0 (length n).
3. Copy nums into ans starting at index n (length n).
4. Return ans.

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Why length 2n? You need one copy of nums in the front and one in the back, so total length is n + n = 2n.
• Why does one loop work? For each i, you know both destinations: index i and index i + n. You can assign both in the same iteration, so you only walk nums once.
• Why is two loops still O(n)? Each loop runs n times; total work is still proportional to n, not n².
• System.arraycopy: The JVM can copy blocks of memory very efficiently (often native code), which can be faster than a hand-written loop for large n, though asymptotic complexity stays O(n).

---

3. The Dry Run

Sample: nums = [1, 2, 1], so n = 3, ans length 6.

Single-loop optimal trace

Step	i	nums[i]	ans[0]	ans[1]	ans[2]	ans[3]	ans[4]	ans[5]
init	—	—	0	0	0	0	0	0
1	0	1	1	0	0	1	0	0
2	1	2	1	2	0	1	2	0
3	2	1	1	2	1	1	2	1

Final ans = [1, 2, 1, 1, 2, 1].

---

4. Java Solution

Brute Force

public int[] getConcatenation(int[] nums) {
    int n = nums.length;
    int[] ans = new int[2 * n];
    for (int i = 0; i < n; i++) {
        ans[i] = nums[i];
    }
    for (int i = 0; i < n; i++) {
        ans[i + n] = nums[i];
    }
    return ans;
}

Time: O(n) — two passes over n elements.
Space: O(n) — output array of size 2n (the problem requires it).

Optimal

public int[] getConcatenation(int[] nums) {
    int n = nums.length;
    int[] ans = new int[2 * n];
    for (int i = 0; i < n; i++) {
        ans[i] = nums[i];
        ans[i + n] = nums[i];
    }
    return ans;
}

Using System.arraycopy (also O(n), often fast in practice)

public int[] getConcatenation(int[] nums) {
    int n = nums.length;
    int[] ans = new int[2 * n];
    System.arraycopy(nums, 0, ans, 0, n);
    System.arraycopy(nums, 0, ans, n, n);
    return ans;
}

Time: O(n).
Space: O(n) for the result array.

---

5. The “Java vs. Others” Edge

• System.arraycopy is a native JVM method that copies ranges quickly; in C/C++ you might use memcpy for similar bulk moves. It is not the same as “concatenate” helpers in higher-level APIs, but it fits this pattern well.
• Arrays.copyOf(nums, 2 * n) only pads or truncates to a new length; it does not duplicate nums twice into one array, so it is not a one-call solution for “double concat” unless you combine it with another copy.
• Fixed-size arrays: In Java, new int[2 * n] has a fixed length. Python lists can .append dynamically; here you must allocate the final size up front (or use a growable structure, which is unnecessary for this problem).
• No built-in array concat: Unlike JavaScript’s [...a, ...a], you typically loop or use System.arraycopy for primitive arrays.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	Two loops; output dominates extra space.
Optimal	O(n)	O(n)	One loop or two arraycopy calls; same asymptotics, fewer iterations in one loop.