Scale Engineer

Concatenation of Array

Easy
#1760Time: 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.1 company
Data structures
Array
Companies
GE Healthcare

Prompt

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.length
  • 1 <= n <= 1000
  • 1 <= 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

    1. Get the length of the input array nums, let's call it n.
    1. Create a new integer array ans of size 2 * n.
    1. Iterate from i = 0 to n - 1. In this first loop, copy the element nums[i] to ans[i].
    1. Iterate again from i = 0 to n - 1. In this second loop, copy the element nums[i] to ans[i + n].
    1. Return the ans array.

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.

Solutions

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 ; } }

Video 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.

← Previous

Previous problem

Next →

Next problem