393. Distribute Elements Into Two Arrays I

Follow the rules literally: seed arr1 and arr2 with the first two elements, then route each remaining element to whichever array currently has the larger tail.

Idea

This is a pure simulation problem — there is no clever trick, just a faithful re-enactment of the rules. We maintain two growing lists, arr1 and arr2, and decide the destination of each element by comparing the last element (the tail) of each list.

Walk-through — nums = [5, 4, 3, 8]

Seed phase (fixed by the rules):

1. Operation 1: append nums[0] = 5 to arr1 → arr1 = [5].
2. Operation 2: append nums[1] = 4 to arr2 → arr2 = [4].

Distribute phase — for every later element compare the tails:

1. Operation 3, nums[2] = 3: tail of arr1 is 5, tail of arr2 is 4. Since 5 > 4, append to arr1 → arr1 = [5, 3].
2. Operation 4, nums[3] = 8: tail of arr1 is 3, tail of arr2 is 4. Since 3 is not greater than 4, append to arr2 → arr2 = [4, 8].

Concatenate: result = arr1 + arr2 = [5, 3] + [4, 8] = [5, 3, 4, 8].

Why the tail is all that matters

Each decision looks only at the current last elements, so we never need to re-scan either list. A single pass with O(1) work per element suffices.

Complexity

• Time: O(n) — one comparison and one append per element.
• Space: O(n) — the two arrays together hold all n elements.

class Solution {
    public int[] resultArray(int[] nums) {
        int n = nums.length;
        int[] arr1 = new int[n];
        int[] arr2 = new int[n];
        int len1 = 0, len2 = 0;
        arr1[len1++] = nums[0];
        arr2[len2++] = nums[1];
        for (int i = 2; i < n; i++) {
            if (arr1[len1 - 1] > arr2[len2 - 1]) {
                arr1[len1++] = nums[i];
            } else {
                arr2[len2++] = nums[i];
            }
        }
        int[] result = new int[n];
        int idx = 0;
        for (int i = 0; i < len1; i++) result[idx++] = arr1[i];
        for (int i = 0; i < len2; i++) result[idx++] = arr2[i];
        return result;
    }
}