Problem

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

You need to distribute all the elements of nums between two arrays arr1 and arr2 using n operations. In the first operation, append nums[1] to arr1. In the second operation, append nums[2] to arr2. Afterwards, in the ith operation:

  • If the last element of arr1 isgreater than the last element of arr2, append nums[i] to arr1. Otherwise, append nums[i] to arr2.

The array result is formed by concatenating the arrays arr1 and arr2. For example, if arr1 == [1,2,3] and arr2 == [4,5,6], then result = [1,2,3,4,5,6].

Return the array result.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    Input: nums = [2,1,3]
    Output: [2,3,1]
    Explanation: After the first 2 operations, arr1 = [2] and arr2 = [1].
    In the 3rd operation, as the last element of arr1 is greater than the last element of arr2 (2 > 1), append nums[3] to arr1.
    After 3 operations, arr1 = [2,3] and arr2 = [1].
    Hence, the array result formed by concatenation is [2,3,1].

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    
    
    Input: nums = [5,4,3,8]
    Output: [5,3,4,8]
    Explanation: After the first 2 operations, arr1 = [5] and arr2 = [4].
    In the 3rd operation, as the last element of arr1 is greater than the last element of arr2 (5 > 4), append nums[3] to arr1, hence arr1 becomes [5,3].
    In the 4th operation, as the last element of arr2 is greater than the last element of arr1 (4 > 3), append nums[4] to arr2, hence arr2 becomes [4,8].
    After 4 operations, arr1 = [5,3] and arr2 = [4,8].
    Hence, the array result formed by concatenation is [5,3,4,8].

Constraints

  • 3 <= n <= 50
  • 1 <= nums[i] <= 100
  • All elements in nums are distinct.

Solution

Method 1 – Simulation

Intuition

We simulate the process as described: start by appending the first element to arr1, the second to arr2, then for each subsequent element, compare the last elements of arr1 and arr2 and append accordingly. Finally, concatenate arr1 and arr2 for the result.

Approach

  1. Initialize arr1 with nums[0] and arr2 with nums[1].
  2. For each index i from 2 to n-1:
    • If the last element of arr1 is greater than the last of arr2, append nums[i] to arr1.
    • Otherwise, append nums[i] to arr2.
  3. Concatenate arr1 and arr2 to form the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<int> resultArray(vector<int>& nums) {
        vector<int> arr1{nums[0]}, arr2{nums[1]};
        for (int i = 2; i < nums.size(); ++i) {
            if (arr1.back() > arr2.back()) arr1.push_back(nums[i]);
            else arr2.push_back(nums[i]);
        }
        vector<int> ans = arr1;
        ans.insert(ans.end(), arr2.begin(), arr2.end());
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func resultArray(nums []int) []int {
    arr1 := []int{nums[0]}
    arr2 := []int{nums[1]}
    for i := 2; i < len(nums); i++ {
        if arr1[len(arr1)-1] > arr2[len(arr2)-1] {
            arr1 = append(arr1, nums[i])
        } else {
            arr2 = append(arr2, nums[i])
        }
    }
    return append(arr1, arr2...)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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[] ans = new int[nums.length];
        int idx = 0;
        for (int x : arr1) ans[idx++] = x;
        for (int x : arr2) ans[idx++] = x;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun resultArray(nums: IntArray): IntArray {
        val arr1 = mutableListOf(nums[0])
        val arr2 = mutableListOf(nums[1])
        for (i in 2 until nums.size) {
            if (arr1.last() > arr2.last()) arr1.add(nums[i])
            else arr2.add(nums[i])
        }
        return (arr1 + arr2).toIntArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn result_array(nums: Vec<i32>) -> Vec<i32> {
        let mut arr1 = vec![nums[0]];
        let mut arr2 = vec![nums[1]];
        for i in 2..nums.len() {
            if arr1[arr1.len() - 1] > arr2[arr2.len() - 1] {
                arr1.push(nums[i]);
            } else {
                arr2.push(nums[i]);
            }
        }
        arr1.extend(arr2);
        arr1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    resultArray(nums: number[]): number[] {
        const arr1 = [nums[0]];
        const arr2 = [nums[1]];
        for (let i = 2; i < nums.length; ++i) {
            if (arr1[arr1.length - 1] > arr2[arr2.length - 1]) arr1.push(nums[i]);
            else arr2.push(nums[i]);
        }
        return arr1.concat(arr2);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each element is processed once.
  • 🧺 Space complexity: O(n), for the two arrays and the result.