3069. Distribute Elements Into Two Arrays I

Problem Overview

arr1 starts with nums[0], arr2 with nums[1].

Intuition

arr1 starts with nums[0], arr2 with nums[1]. Each later element goes to whichever array has the larger last value (ties go to arr2). There is no lookahead - just simulate and concatenate arr1 then arr2.

Algorithm

1Write nums[0] to arr1 and nums[1] to arr2; track last1 and last2.
2For k from 2 to n-1: if last1 > last2 append nums[k] to arr1, else to arr2; update the matching last.
3Copy arr1 then arr2 into the result array of length n.
4Return the merged array.

Example Walkthrough

Input: nums = [2, 1, 3]

1.Start arr1=[2], arr2=[1]. last1=2, last2=1.
2.2 > 1 so 3 goes to arr1 -> arr1=[2,3], arr2=[1].
3.Result is [2, 3, 1].

Output: [2, 3, 1]

Common Pitfalls

•When last1 == last2, the next element must go to arr2, not arr1.
•The first two elements are fixed - the loop starts at index 2.
•Result order is arr1 followed by arr2, not interleaved.
•n is at least 3 per constraints.

3069.cs

// Approach: Simulate the rules. Keep arr1 ending at last1 and arr2 at last2;
// from index 2 onward, append nums[i] to the array whose tail is larger (else
// arr2). Write both halves into one result array.
// Complexity: O(n) time and O(n) space.
public class Solution
{
    public int[] ResultArray(int[] nums)
    {
        int n = nums.Length;
        int[] arr1 = new int[n];
        int[] arr2 = new int[n];
        arr1[0] = nums[0];
        arr2[0] = nums[1];
        int i = 0, j = 0;
        int last1 = nums[0], last2 = nums[1];

        for (int k = 2; k < n; k++)
        {
            if (last1 > last2)
                last1 = arr1[++i] = nums[k];
            else
                last2 = arr2[++j] = nums[k];
        }

        int[] ans = new int[n];
        Array.Copy(arr1, 0, ans, 0, i + 1);
        Array.Copy(arr2, 0, ans, i + 1, j + 1);
        return ans;
    }
}

Was this solution helpful?