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 <= 501 <= nums[i] <= 100All elements in nums are distinct.
Hints for Distribute Elements Into Two Arrays I
Hint 1
Simulate exactly as written; there is no shortcut.
Hint 2
Only the last element of each array matters for the decision.
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
- Put
nums[0]inarr1andnums[1]inarr2. - For each later element, compare the two arrays' last values.
- Append to
arr1when its last is strictly greater, otherwise toarr2. - Return
arr1concatenated witharr2.
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 + bJava
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