Distribute Elements Into Two Arrays I

Easy
990.

Distribute Elements Into Two Arrays I

Distribute Elements Into Two Arrays I is an easy coding problem on arrays and simulation, asked in Amazon, Google and Accenture interviews.

Distribute the elements of nums into two arrays arr1 and arr2 in n operations. The first element goes to arr1 and the second to arr2.

After that, element i goes to arr1 if the last element of arr1 is greater than the last element of arr2, and to arr2 otherwise. Return arr1 followed by arr2.

Example 1

Input
nums = [2,1,3]
Output
[2,3,1]
Explanation
`arr1 = [2]`, `arr2 = [1]`; 2 > 1 so the 3 joins `arr1`.

Example 2

Input
nums = [5,4,3,8]
Output
[5,3,4,8]

Example 3

Input
nums = [1,2]
Output
[1,2]

Constraints

  • 2 <= nums.length <= 50
  • 1 <= nums[i] <= 100
  • All elements in nums are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var resultArray = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Distribute Elements Into Two Arrays I — Problem & Solution

Distribute Elements Into Two Arrays I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Distribute Elements Into Two Arrays I is an easy coding problem on arrays and simulation, asked in Amazon, Google and Accenture interviews.

  • Difficulty: Easy
  • Topics: Arrays, Simulation
  • Asked at: Amazon, Google, Accenture
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Distribute the elements of nums into two arrays arr1 and arr2 in n operations. The first element goes to arr1 and the second to arr2.

After that, element i goes to arr1 if the last element of arr1 is greater than the last element of arr2, and to arr2 otherwise. Return arr1 followed by arr2.

Example 1

Input: nums = [2,1,3]
Output: [2,3,1]
Explanation: `arr1 = [2]`, `arr2 = [1]`; 2 > 1 so the 3 joins `arr1`.

Example 2

Input: nums = [5,4,3,8]
Output: [5,3,4,8]

Example 3

Input: nums = [1,2]
Output: [1,2]

Constraints

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

Hints for Distribute Elements Into Two Arrays I

  1. Hint 1

    Simulate exactly as written; there is no shortcut.

  2. Hint 2

    Only the last element of each array matters for the decision.

  3. Hint 3

    Concatenate at the end, not as you go.

How to solve Distribute Elements Into Two Arrays I

Straight simulation. Seed the two arrays with the first two elements, then append each remaining element to whichever array currently ends larger, defaulting to arr2 on a tie.

Approach

  1. Put nums[0] in arr1 and nums[1] in arr2.
  2. For each later element, compare the two arrays' last values.
  3. Append to arr1 when its last is strictly greater, otherwise to arr2.
  4. Return arr1 concatenated with arr2.

Why it works

Only the tails matter, so each step is O(1) and the whole thing is one pass. The elements are distinct, so the > test never actually ties — but writing the fallback as arr2 matches the statement exactly and keeps the code honest if that guarantee were relaxed.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The decision uses the last element, not the maximum or the length.
  • The first two placements are fixed and not decided by the rule.
  • Concatenating in the wrong order reverses the answer.

Reference solution

Python

from typing import List

def resultArray(nums: List[int]) -> List[int]:
    a = [nums[0]]
    b = [nums[1]]
    for v in nums[2:]:
        if a[-1] > b[-1]:
            a.append(v)
        else:
            b.append(v)
    return a + b

Java

public static int[] resultArray(int[] nums) {
    List<Integer> a = new ArrayList<>();
    List<Integer> b = new ArrayList<>();
    a.add(nums[0]);
    b.add(nums[1]);
    for (int i = 2; i < nums.length; i++) {
        if (a.get(a.size() - 1) > b.get(b.size() - 1)) a.add(nums[i]);
        else b.add(nums[i]);
    }
    int[] out = new int[nums.length];
    int k = 0;
    for (int v : a) out[k++] = v;
    for (int v : b) out[k++] = v;
    return out;
}

C++

vector<int> resultArray(vector<int>& nums) {
    vector<int> a = { nums[0] }, b = { nums[1] };
    for (size_t i = 2; i < nums.size(); i++) {
        if (a.back() > b.back()) a.push_back(nums[i]);
        else b.push_back(nums[i]);
    }
    a.insert(a.end(), b.begin(), b.end());
    return a;
}

JavaScript

var resultArray = function(nums) {
    var a = [nums[0]], b = [nums[1]];
    for (var i = 2; i < nums.length; i++) {
        if (a[a.length - 1] > b[b.length - 1]) a.push(nums[i]);
        else b.push(nums[i]);
    }
    return a.concat(b);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays