Result of the Prescribed Two-Array Distribution
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
# Result of the Prescribed Two-Array Distribution
You are given an array `nums` of distinct positive integers. Distribute its elements between two initially empty arrays, `arr1` and `arr2`, in input order.
Using the C++ vector's zero-based indices:
1. Append `nums[0]` to `arr1`.
2. Append `nums[1]` to `arr2`.
3. For each remaining element `nums[i]`, if the last element of `arr1` is greater than the last element of `arr2`, append `nums[i]` to `arr1`. Otherwise, append it to `arr2`.
Return `arr1` followed by `arr2` as one concatenated array. Preserve the append order within each array.
### Examples
**Example 1**
```text
Input: nums = [6,2,5,1,7]
Output: [6,5,1,2,7]
```
Initialization gives `arr1 = [6]` and `arr2 = [2]`. Values `5` and `1` are appended to `arr1`, because its last value is greater at each decision. The final value `7` goes to `arr2`, since its current last value `2` is greater than `arr1`'s last value `1`. The final arrays are `[6,5,1]` and `[2,7]`.
**Example 2**
```text
Input: nums = [3,7,1,6,8,2]
Output: [3,6,8,2,7,1]
```
After initialization, `1` goes to `arr2`, making its last value `1`. The remaining values `6`, `8`, and `2` each go to `arr1`. The final arrays are `[3,6,8,2]` and `[7,1]`.
### Constraints
- `n == nums.length`.
- `3 <= n <= 50`.
- `1 <= nums[i] <= 100`.
- All elements of `nums` are distinct.
### Clarifying Questions
- Is the next element compared with the last values? No; compare the two arrays' last values to choose its destination.
- Are elements processed after sorting? No; process them in the given input order.
- Can elements be rearranged within a destination array? No; each new element is appended at the end.
- Are the two destination arrays interleaved in the result? No; return all of `arr1`, then all of `arr2`.
### C++ Interface
```cpp
class Solution {
public:
vector<int> resultArray(vector<int>& nums) {
}
};
```
### Reasoning Checkpoints
- Follow initialization and every routing decision in input order.
- Preserve each destination's append order and the specified concatenation order.
- Justify correctness and resource costs for the stated input domain.
```hint Keep the current destination arrays
Both arrays are nonempty after the first two elements. Store their elements and consult their current last values before appending the next input element.
```
Overview: Apply the prescribed distribution of distinct input values into two arrays and return their ordered concatenation, with every routing decision explained.