Skip to content

3069. Distribute Elements Into Two Arrays I

Description

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 is greater 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.

Β 

Example 1:

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:

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.

Solutions

Solution 1: Simulation

We create two arrays \(\textit{arr1}\) and \(\textit{arr2}\) to store the elements of \(\textit{nums}\). Initially, \(\textit{arr1}\) contains only \(\textit{nums[0]}\), and \(\textit{arr2}\) contains only \(\textit{nums[1]}\).

Then we iterate over the elements of \(\textit{nums}\) starting from index \(2\). If the last element of \(\textit{arr1}\) is greater than the last element of \(\textit{arr2}\), we append the current element to \(\textit{arr1}\); otherwise, we append it to \(\textit{arr2}\).

Finally, we append the elements of \(\textit{arr2}\) to \(\textit{arr1}\) and return \(\textit{arr1}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).

 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 x in nums[2:]:
            if arr1[-1] > arr2[-1]:
                arr1.append(x)
            else:
                arr2.append(x)
        return arr1 + arr2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
        for (int k = 2; k < n; ++k) {
            if (arr1[i] > arr2[j]) {
                arr1[++i] = nums[k];
            } else {
                arr2[++j] = nums[k];
            }
        }
        for (int k = 0; k <= j; ++k) {
            arr1[++i] = arr2[k];
        }
        return arr1;
    }
}

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

 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 _, x := range nums[2:] {
        if arr1[len(arr1)-1] > arr2[len(arr2)-1] {
            arr1 = append(arr1, x)
        } else {
            arr2 = append(arr2, x)
        }
    }
    return append(arr1, arr2...)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function resultArray(nums: number[]): number[] {
    const arr1: number[] = [nums[0]];
    const arr2: number[] = [nums[1]];
    for (const x of nums.slice(2)) {
        if (arr1.at(-1)! > arr2.at(-1)!) {
            arr1.push(x);
        } else {
            arr2.push(x);
        }
    }
    return arr1.concat(arr2);
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int[] ResultArray(int[] nums) {
        int n = nums.Length;
        var arr1 = new List<int> { nums[0] };
        var arr2 = new List<int> { nums[1] };

        for (int k = 2; k < n; ++k) {
            if (arr1[arr1.Count - 1] > arr2[arr2.Count - 1]) {
                arr1.Add(nums[k]);
            } else {
                arr2.Add(nums[k]);
            }
        }

        arr1.AddRange(arr2);
        return arr1.ToArray();
    }
}

Comments