Distribute Elements Into Two Arrays I

Difficulty: Easy | Acceptance: 74.00% | Paid: No Topics: Array, Simulation

You are given a 1-indexed integer array nums of length n.

You are given a 1-indexed integer array nums of length n.

We distribute the elements of nums into two arrays arr1 and arr2 using n operations, where the ith operation starts from the ith element in nums.

The rules for the ith operation (1-indexed) are:

• If the last element of arr1 is greater than the last element of arr2, append nums[i] to arr1. Otherwise, append nums[i] to arr2.
• The first two elements are assigned to arr1 and arr2 respectively before the loop starts.

The result array is formed by concatenating arr1 followed by arr2.

Return the result array.

• Examples
• Constraints
• Direct Simulation
• Two-Pointer Construction

Examples

Input: nums = [2,1,3]
Output: [2,3,1]
Explanation: 
- Operation 1: nums[0] is 2. arr1 = [2], arr2 = [].
- Operation 2: nums[1] is 1. arr1 = [2], arr2 = [1].
- Operation 3: nums[2] is 3. Since 2 > 1, append to arr1. arr1 = [2,3], arr2 = [1].
- Result: [2,3,1].

Input: nums = [5,4,3,3]
Output: [5,3,4,3]
Explanation:
- Operation 1: nums[0] is 5. arr1 = [5], arr2 = [].
- Operation 2: nums[1] is 4. arr1 = [5], arr2 = [4].
- Operation 3: nums[2] is 3. Since 5 > 4, append to arr1. arr1 = [5,3], arr2 = [4].
- Operation 4: nums[3] is 3. Since 3 is not greater than 3, append to arr2. arr1 = [5,3], arr2 = [4,3].
- Result: [5,3,4,3].

Constraints

3 <= nums.length <= 50
1 <= nums[i] <= 100

Direct Simulation

Intuition We can strictly follow the problem’s rules by iterating through the input array and maintaining two separate lists for the results.

Steps

• Initialize arr1 with the first element and arr2 with the second element of nums.
• Iterate through the rest of the elements starting from index 2.
• Compare the last elements of arr1 and arr2.
• Append the current element to the array with the larger last element.
• Concatenate arr1 and arr2 and return the result.

class Solution:
    def resultArray(self, nums: list[int]) -> list[int]:
        arr1 = [nums[0]]
        arr2 = [nums[1]]
        for i in range(2, len(nums)):
            if arr1[-1] > arr2[-1]:
                arr1.append(nums[i])
            else:
                arr2.append(nums[i])
        return arr1 + arr2

Complexity

• Time: O(n) - We iterate through the array once.
• Space: O(n) - We store the elements in two auxiliary arrays.
• Notes: This is the most straightforward approach and is efficient enough given the constraints.

Two-Pointer Construction

Intuition We can optimize space usage by pre-allocating a single result array and filling it from both ends using two pointers, then merging the two parts.

Steps

• Create a result array of size n.
• Place the first element at index 0 and the second at index 1.
• Initialize pointers l = 1 (end of arr1) and r = n - 1 (start of arr2 from the end).
• Iterate through the remaining elements.
• If the element at l is greater than the element at r, increment l and place the current element there.
• Otherwise, decrement r and place the current element there.
• Return the concatenation of the segment 0 to l and r to n-1.

class Solution:
    def resultArray(self, nums: list[int]) -> list[int]:
        n = len(nums)
        res = [0] * n
        res[0] = nums[0]
        res[1] = nums[1]
        l, r = 1, n - 1
        for i in range(2, n):
            if res[l] > res[r]:
                l += 1
                res[l] = nums[i]
            else:
                r -= 1
                res[r] = nums[i]
        return res[:l+1] + res[r:]

Complexity

• Time: O(n) - Single pass to fill the array and O(n) to construct the final result.
• Space: O(n) - For the result array.
• Notes: This approach avoids using dynamic list resizing operations (like push_back or append) repeatedly, though the overall complexity remains linear.