Concatenation of Array
EasyPrompt
Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).
Specifically, ans is the concatenation of two nums arrays.
Return the array ans.
Example 1:
Input: nums = [1,2,1]
Output: [1,2,1,1,2,1]
Explanation: The array ans is formed as follows:
- ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
- ans = [1,2,1,1,2,1]Example 2:
Input: nums = [1,3,2,1]
Output: [1,3,2,1,1,3,2,1]
Explanation: The array ans is formed as follows:
- ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]]
- ans = [1,3,2,1,1,3,2,1]
Constraints:
n == nums.length1 <= n <= 10001 <= nums[i] <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves creating a new array of double the size and then iterating through the input array twice. The first iteration copies the elements to the first half of the new array, and the second iteration copies them to the second half.
Algorithm
-
- Get the length of the input array
nums, let's call itn.
- Get the length of the input array
-
- Create a new integer array
ansof size2 * n.
- Create a new integer array
-
- Iterate from
i = 0ton - 1. In this first loop, copy the elementnums[i]toans[i].
- Iterate from
-
- Iterate again from
i = 0ton - 1. In this second loop, copy the elementnums[i]toans[i + n].
- Iterate again from
-
- Return the
ansarray.
- Return the
Walkthrough
This approach is straightforward. We first allocate an array ans with a size of 2 * n, where n is the length of the input array nums. Then, we use two separate loops to populate this new array. The first loop fills the first n elements of ans, and the second loop fills the remaining n elements. While simple, it's slightly less efficient than a single-loop solution because it requires two separate passes over the data.
Here is the Java implementation:
class Solution { public int[] getConcatenation(int[] nums) { int n = nums.length; int[] ans = new int[2 * n]; // First loop to copy nums to the first half of ans for (int i = 0; i < n; i++) { ans[i] = nums[i]; } // Second loop to copy nums to the second half of ans for (int i = 0; i < n; i++) { ans[i + n] = nums[i]; } return ans; }}Complexity
Time
O(n), where n is the length of the `nums` array. We iterate through the `nums` array twice, once for the first half of `ans` and once for the second half. The total number of operations is proportional to n + n = 2n, which simplifies to O(n).
Space
O(n), as we create a new array `ans` of size 2n. The space required is proportional to the size of the input array. Note that the problem requires returning a new array, so this space is unavoidable.
Trade-offs
Pros
Very simple to understand and implement.
Cons
Slightly less efficient than a single-loop approach as it iterates over the input array twice.
Code is more verbose than necessary.
A more efficient approach is to use a single loop. In each iteration, we can place the current element at two positions in the new array: its original position i and its concatenated position i + n.
Algorithm
-
- Get the length of the input array
nums, let's call itn.
- Get the length of the input array
-
- Create a new integer array
ansof size2 * n.
- Create a new integer array
-
- Iterate from
i = 0ton - 1. In each iteration, perform two assignments:
- Set
ans[i]tonums[i]. - Set
ans[i + n]tonums[i].
- Iterate from
-
- After the loop completes, return the
ansarray.
- After the loop completes, return the
Walkthrough
This method improves upon the brute-force approach by consolidating the two loops into one. We iterate through the input array nums just once. For each index i from 0 to n-1, we know that the element nums[i] needs to be placed at ans[i] and ans[i + n]. By performing both assignments within the same loop, we make the code more concise and slightly more performant by reducing loop overhead.
Here is the Java implementation:
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; }}Complexity
Time
O(n), where n is the length of the `nums` array. We iterate through the input array only once, performing a constant number of operations in each iteration. This is the most optimal time complexity possible as we must touch each element at least once.
Space
O(n), as we need to create a result array `ans` of size 2n. This space is required by the problem statement.
Trade-offs
Pros
More efficient than the two-loop approach as it reduces loop overhead.
Clean and concise code.
Optimal time and space complexity for the given constraints.
Cons
No significant cons, this is an optimal solution for this problem.
Solutions
Solution
class Solution { public int [] getConcatenation ( int [] nums ) { int n = nums . length ; int [] ans = new int [ n << 1 ]; for ( int i = 0 ; i < n << 1 ; ++ i ) { ans [ i ] = nums [ i % n ]; } return ans ; } }/** * @param {number[]} nums * @return {number[]} */ var getConcatenation = function (nums) { let ans = nums.slice(); ans.splice(nums.length, 0, ...nums); return ans; };class Solution { public: vector < int > getConcatenation ( vector < int >& nums ) { for ( int i = 0 , n = nums . size (); i < n ; ++ i ) { nums . push_back ( nums [ i ]); } return nums ; } };class Solution: def getConcatenation( self, nums: List[int]) -> List[int]: return nums + numsVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.