Jobs

Interviews

Discussions

Concatenation of Array

Easy

Asked by:

More companies

84 views

Topics:

Arrays

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

Try coding it in LeetCode

Concatenation of Array

Easy

Asked by:

84 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `nums`?
Can the input array `nums` contain negative integers, zero, or only positive integers?
Should I create a new array in memory or is modifying the original array allowed (if that were possible given the problem description)?
Is there a specific data type I should use for the returned array (e.g., `int`, `long`)?
Is the input array guaranteed to be non-null and non-empty?

Brute Force Solution

Approach

The brute force approach to concatenating an array involves creating a new array that's twice the size of the original. We then directly copy the elements from the original array into the first half and then again into the second half.

Here's how the algorithm would work step-by-step:

First, create a brand new, bigger container that can hold twice as many items as the original container.
Next, take each item from the original container and put it into the bigger container in the same order.
Then, repeat the process: again take each item from the original container and add it to the bigger container, continuing in the same order from where you left off.
Finally, the bigger container now holds a copy of the original container right next to another copy of the original container.

Code Implementation

def concatArrayBruteForce(originalArray):

    arrayLength = len(originalArray)
    # Create a new array with double the size of original
    concatenatedArray = [0] * (2 * arrayLength)

    # Copy the elements from the original array
    for index in range(arrayLength):
        concatenatedArray[index] = originalArray[index]

    # Copy the original array again to the second half
    for index in range(arrayLength):

        secondHalfIndex = index + arrayLength
        concatenatedArray[secondHalfIndex] = \
            originalArray[index]

    return concatenatedArray

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums once to copy its elements into the first half of the ans array. Then, it iterates through nums again to copy its elements into the second half of the ans array. Each iteration involves a constant-time assignment operation. Therefore, the overall time complexity is proportional to 2n, which simplifies to O(n), where n is the length of the input array.

Space Complexity

O(N) – The provided solution creates a new array to store the concatenation. The size of this new array is twice the size of the original input array. Therefore, the auxiliary space used is directly proportional to the input size N, where N is the number of elements in the original array. This results in a space complexity of O(N).

Optimal Solution

Approach

We want to create a new, longer list by simply sticking the original list to the end of itself. The best way to do this is by figuring out how long the final list needs to be and then filling it piece by piece in a clever way.

Here's how the algorithm would work step-by-step:

First, figure out the length of the original list. This will help you understand the size of the new, combined list you need to make.
Create a new list that is exactly twice as long as the original list.
Now, copy everything from the original list into the first half of the new list.
Then, copy everything from the original list again, but this time put it into the second half of the new list.
You've now created a list that is exactly the original list stuck to the end of itself. You're done!

Code Implementation

def concatenation_of_array(original_list):
    original_length = len(original_list)

    # The new list needs to be twice the size of the original.
    concatenated_list = [0] * (2 * original_length)

    # Copy the original list to the first half of the new list.
    for index in range(original_length):
        concatenated_list[index] = original_list[index]

    # Copy the original list again to the second half of the new list.
    for index in range(original_length):
        concatenated_list[index + original_length] = original_list[index]

    return concatenated_list

Big(O) Analysis

Time Complexity

O(n) – The algorithm's runtime is determined by the copying of the original array's elements into the new array. It iterates through the original array of size n twice, once to fill the first half of the new array and again to fill the second half. Therefore, the number of operations scales linearly with the size of the input array n, resulting in a time complexity of O(n).

Space Complexity

O(N) – The provided solution creates a new list that is twice the length of the original input list. This new list is the primary driver of space complexity. Therefore, the auxiliary space required is directly proportional to the size of the input list, which we denote as N. Thus, an array of size 2N is allocated, which simplifies to O(N) space complexity.

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return null to indicate invalid input, depending on requirements.
Empty input array	Return an empty array as the concatenation of an empty array with itself is an empty array.
Array with a single element	The concatenation will be an array with two identical elements; handle normally.
Array with maximum allowed size (e.g., Integer.MAX_VALUE) leading to potential memory overflow	Ensure the target programming language and environment can allocate sufficient memory or return an error if allocation fails.
Array containing Integer.MAX_VALUE or Integer.MIN_VALUE	The solution should handle these extreme values without causing integer overflow errors, assuming operations like addition or multiplication are not performed on the numbers.
Array with all identical values	The concatenation will simply be the array repeated twice, which the general algorithm handles correctly.
Array with negative numbers	The solution should handle negative numbers correctly, as they are valid integers and should be concatenated normally.
Array with zero values	Zero values should be treated as any other integer and handled correctly during concatenation.

Null input array

How to Handle:

Throw an IllegalArgumentException or return null to indicate invalid input, depending on requirements.

Empty input array

How to Handle:

Return an empty array as the concatenation of an empty array with itself is an empty array.

Array with a single element

How to Handle:

The concatenation will be an array with two identical elements; handle normally.

Array with maximum allowed size (e.g., Integer.MAX_VALUE) leading to potential memory overflow

How to Handle:

Ensure the target programming language and environment can allocate sufficient memory or return an error if allocation fails.

Array containing Integer.MAX_VALUE or Integer.MIN_VALUE

How to Handle:

The solution should handle these extreme values without causing integer overflow errors, assuming operations like addition or multiplication are not performed on the numbers.

Array with all identical values

How to Handle:

The concatenation will simply be the array repeated twice, which the general algorithm handles correctly.

Array with negative numbers

How to Handle:

The solution should handle negative numbers correctly, as they are valid integers and should be concatenated normally.

Array with zero values

How to Handle:

Zero values should be treated as any other integer and handled correctly during concatenation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `nums`?
Can the input array `nums` contain negative integers, zero, or only positive integers?
Should I create a new array in memory or is modifying the original array allowed (if that were possible given the problem description)?
Is there a specific data type I should use for the returned array (e.g., `int`, `long`)?
Is the input array guaranteed to be non-null and non-empty?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a brand new, bigger container that can hold twice as many items as the original container.
Next, take each item from the original container and put it into the bigger container in the same order.
Then, repeat the process: again take each item from the original container and add it to the bigger container, continuing in the same order from where you left off.
Finally, the bigger container now holds a copy of the original container right next to another copy of the original container.

Code Implementation

def concatArrayBruteForce(originalArray):

    arrayLength = len(originalArray)
    # Create a new array with double the size of original
    concatenatedArray = [0] * (2 * arrayLength)

    # Copy the elements from the original array
    for index in range(arrayLength):
        concatenatedArray[index] = originalArray[index]

    # Copy the original array again to the second half
    for index in range(arrayLength):

        secondHalfIndex = index + arrayLength
        concatenatedArray[secondHalfIndex] = \
            originalArray[index]

    return concatenatedArray

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out the length of the original list. This will help you understand the size of the new, combined list you need to make.
Create a new list that is exactly twice as long as the original list.
Now, copy everything from the original list into the first half of the new list.
Then, copy everything from the original list again, but this time put it into the second half of the new list.
You've now created a list that is exactly the original list stuck to the end of itself. You're done!

Code Implementation

def concatenation_of_array(original_list):
    original_length = len(original_list)

    # The new list needs to be twice the size of the original.
    concatenated_list = [0] * (2 * original_length)

    # Copy the original list to the first half of the new list.
    for index in range(original_length):
        concatenated_list[index] = original_list[index]

    # Copy the original list again to the second half of the new list.
    for index in range(original_length):
        concatenated_list[index + original_length] = original_list[index]

    return concatenated_list

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return null to indicate invalid input, depending on requirements.
Empty input array	Return an empty array as the concatenation of an empty array with itself is an empty array.
Array with a single element	The concatenation will be an array with two identical elements; handle normally.
Array with maximum allowed size (e.g., Integer.MAX_VALUE) leading to potential memory overflow	Ensure the target programming language and environment can allocate sufficient memory or return an error if allocation fails.
Array containing Integer.MAX_VALUE or Integer.MIN_VALUE	The solution should handle these extreme values without causing integer overflow errors, assuming operations like addition or multiplication are not performed on the numbers.
Array with all identical values	The concatenation will simply be the array repeated twice, which the general algorithm handles correctly.
Array with negative numbers	The solution should handle negative numbers correctly, as they are valid integers and should be concatenated normally.
Array with zero values	Zero values should be treated as any other integer and handled correctly during concatenation.

Null input array

How to Handle:

Throw an IllegalArgumentException or return null to indicate invalid input, depending on requirements.

Empty input array

How to Handle:

Return an empty array as the concatenation of an empty array with itself is an empty array.

Array with a single element

How to Handle:

The concatenation will be an array with two identical elements; handle normally.

Array with maximum allowed size (e.g., Integer.MAX_VALUE) leading to potential memory overflow

How to Handle:

Ensure the target programming language and environment can allocate sufficient memory or return an error if allocation fails.

Array containing Integer.MAX_VALUE or Integer.MIN_VALUE

How to Handle:

The solution should handle these extreme values without causing integer overflow errors, assuming operations like addition or multiplication are not performed on the numbers.

Array with all identical values

How to Handle:

The concatenation will simply be the array repeated twice, which the general algorithm handles correctly.

Array with negative numbers

How to Handle:

The solution should handle negative numbers correctly, as they are valid integers and should be concatenated normally.

Array with zero values

How to Handle:

Zero values should be treated as any other integer and handled correctly during concatenation.