3069. Distribute Elements Into Two Arrays I

Array
Simulation

TIME

O(n)

SPACE

O(n)

Intuition

The rule is stated procedurally and depends only on the two arrays' last elements, so there is nothing to optimize, just follow it step by step. Each array is append-only, so its last element is always available in O(1).

Approach

Seed arr1 = [nums[0]] and arr2 = [nums[1]] (the first two operations are fixed).
For each remaining element x:
- If arr1[-1] > arr2[-1], append x to arr1.
- Otherwise append x to arr2.
Return arr1 + arr2.

Complexity

Time: O(n), one pass, O(1) per element
Space: O(n), the two arrays / the result

Edge Cases

n >= 3 per constraints, so both seed operations always happen
Elements are distinct, so the two last elements are never equal, the tie branch is unreachable, but "otherwise → arr2" covers it anyway
The comparison is strict (>); only a strictly larger arr1 tail sends the element to arr1
The result is a concatenation, not an interleaving

Code

from typing import List


class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        """
        3069. Distribute Elements Into Two Arrays I
        Time: O(n)
        Space: O(n)
        """
        arr1 = [nums[0]]
        arr2 = [nums[1]]

        for x in nums[2:]:
            if arr1[-1] > arr2[-1]:
                arr1.append(x)
            else:
                arr2.append(x)

        return arr1 + arr2

import java.util.ArrayList;
import java.util.List;

/**
 * 3069. Distribute Elements Into Two Arrays I
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public int[] resultArray(int[] nums) {
        List<Integer> arr1 = new ArrayList<>();
        List<Integer> arr2 = new ArrayList<>();
        arr1.add(nums[0]);
        arr2.add(nums[1]);

        for (int i = 2; i < nums.length; i++) {
            if (arr1.get(arr1.size() - 1) > arr2.get(arr2.size() - 1)) {
                arr1.add(nums[i]);
            } else {
                arr2.add(nums[i]);
            }
        }

        int[] result = new int[nums.length];
        int idx = 0;
        for (int v : arr1) {
            result[idx++] = v;
        }
        for (int v : arr2) {
            result[idx++] = v;
        }
        return result;
    }
}