Concatenation of Array

NeetCode: Concatenation of Array · LeetCode: 1929. Concatenation of Array · Difficulty: Easy

Given an integer array nums of length n, return an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n. In other words, ans is nums followed by nums.

Example

Text

Input:  nums = [1, 2, 1]    Output: [1, 2, 1, 1, 2, 1]
Input:  nums = [1, 3, 2, 1] Output: [1, 3, 2, 1, 1, 3, 2, 1]

Brute force: fill by index

A Java array has a fixed length, so allocate 2n slots and write each element to both positions i and i + n.

Java

import java.util.Arrays;

class Solution {
    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;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.getConcatenation(new int[]{1, 2, 1})));
        System.out.println(Arrays.toString(s.getConcatenation(new int[]{1, 3, 2, 1})));
        System.out.println(Arrays.toString(s.getConcatenation(new int[]{})));
    }
}

Output

[1, 2, 1, 1, 2, 1]
[1, 3, 2, 1, 1, 3, 2, 1]
[]

Time: O(n). Space: O(n) for the answer.

Optimal: copy the block twice

Any solution must write 2n values, so O(n) is optimal. System.arraycopy(src, srcPos, dest, destPos, length) copies a block of elements in one call, so two calls replace the loop.

Java

import java.util.Arrays;

class Solution {
    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;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.getConcatenation(new int[]{1, 2, 1})));
        System.out.println(Arrays.toString(s.getConcatenation(new int[]{1, 3, 2, 1})));
        System.out.println(Arrays.toString(s.getConcatenation(new int[]{})));
    }
}

Output

[1, 2, 1, 1, 2, 1]
[1, 3, 2, 1, 1, 3, 2, 1]
[]

Time: O(n). Space: O(n).

new int[2 * n] sets the final size up front, so the array never has to grow. An empty input gives an empty array, and Arrays.toString prints it as [].