Unpacking "Concatenation of Array": My First Dive into LeetCode (Java)

Today, I’ll kick things off with a fundamental array problem: "Concatenation of Array" (LeetCode #1929). This problem is a great starting point for understanding array manipulation and basic indexing.

Understanding the Problem:

The problem asks us to take an integer array nums of length n, and create a new array, ans, that is twice the length (2n). The ans array should be formed by concatenating nums with itself.

Basically, if nums = [a, b, c], then ans should be [a, b, c, a, b, c].

Let's look at an example:

• Input: nums = [1, 2, 1]

• Length (n): 3

• Expected Output (ans): [1, 2, 1, 1, 2, 1]

The problem specifies ans[i] == nums[i] for the first half, and ans[i + n] == nums[i] for the second half. This means the element at index i in the original array nums should appear at both i and i + n in the new ans array.

My Thought Process & Approach:

When I first read this, the core idea was pretty straightforward: I need a new array that's double the size of the original. Then, I need to fill this new array.

1. Determine n: The first step is to get the length of the input array nums. This n will be crucial for defining the size of our new array and for managing indices.

2. Initialize result array: Create a new array, let's call it result (or ans as per the problem), with a size of 2 * n.

3. Handle Edge Case (Empty Array): What if nums is empty? The problem statement implies n can be 0. If n is 0, 2*n is 0, and returning an empty array is correct. My code includes a check for n==0 which handles this explicitly.

4. Populate the result array: This is the core logic. I need a loop that iterates 2 * n times (covering every index in the result array).

   • First Half: For indices i from 0 up to n-1, the value result[i] should be nums[i].

   • Second Half: For indices i from n up to 2n-1, the value result[i] should be nums[i-n]. This i-n is key because it brings the index back to the 0 to n-1 range of the original nums array. For example, if n=3, when i=3, result[3] needs to be nums[0]. 3-3 = 0. When i=4, result[4] needs to be nums[1]. 4-3 = 1. This logic works perfectly.

Java Code Implementation:

class Solution {
    public int[] getConcatenation(int[] nums) {
        int n = nums.length;
        int[] result = new int[2*n];
        if(n==0){
            return result;
        }
        for(int i = 0;i<2*n;i++){
            if(i<n){
            result[i] = nums[i];
            }
            else{
                result[i] = nums[i-n];
            }
        }
        return result;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(n)

  • We iterate through the input array nums effectively once (or rather, we iterate 2n times, but it's directly proportional to n). Each operation inside the loop (assignment) takes constant time. Therefore, the time complexity grows linearly with the size of the input array n.

• Space Complexity: O(n)

  • We create a new array result whose size is 2 * n. The space required grows linearly with the size of the input array n.