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:
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 <= 501 <= nums[i] <= 100nums are distinct.Problem Overview: You are given an integer array nums. Start two arrays: arr1 with nums[0] and arr2 with nums[1]. For every remaining element, compare the last elements of both arrays. If the last value in arr1 is greater than the last value in arr2, append the current number to arr1; otherwise append it to arr2. After processing all elements, return the concatenation of arr1 followed by arr2. The task is essentially a controlled array construction problem using simple simulation.
Approach 1: Using Hash Maps (O(n) time, O(n) space)
Track the last value of each constructed array using a small hash map keyed by array index (1 for arr1, 2 for arr2). Iterate through nums starting from index 2. On each step, read the stored last values, compare them, and append the current element to the appropriate array. Update the map entry to reflect the new last value. Hash lookups are constant time, so each iteration performs only a few comparisons and updates. This approach keeps the logic explicit and easy to follow, which is useful when extending the rule set or debugging the distribution process.
Approach 2: In-place Marking (O(n) time, O(1) extra space)
Instead of storing extra structures, reuse the input array to mark which target array each element belongs to. Maintain two variables holding the latest values of arr1 and arr2. During a single pass through nums, compare these values and mark the current index accordingly (for example, with a small flag array or encoded value). After the pass, perform a second traversal to build the final result by first collecting elements assigned to arr1 and then those assigned to arr2. The comparison logic stays the same, but auxiliary memory is minimized.
Recommended for interviews: The straightforward simulation approach (tracking the last elements and appending during iteration) is what most interviewers expect. It demonstrates that you correctly interpret the rule and implement efficient array operations in O(n) time. Showing awareness of a space-optimized variation, such as in-place marking, signals deeper understanding of memory tradeoffs.
This approach leverages hash maps (or dictionaries) to store and retrieve elements quickly. The idea is to traverse the data structure and keep track of elements, which allows for efficient lookups and updates. This can help solve problems like finding duplicates, counting frequencies, or intersection of elements.
This C solution uses a simple array to simulate a hash map for storing the frequency of occurrences of elements. It initializes the mapping array, counts frequencies, and then collects elements which have duplicates. The final array contains all duplicate elements.
Time Complexity: O(n + k), where n is the number of elements, and k is the size of the array used as hash map.
Space Complexity: O(k), where k is the size needed for the hash map.
This method involves manipulating the input data structure to keep track of visited elements. It's usually employed when the modification of input is allowed, and we can utilize specific properties of the elements, like their range.
This C solution marks visiting elements by negating the value at the index corresponding to the value of the current element. If an index is found already negative during a visit, the element is a duplicate.
Time Complexity: O(n), where n is the number of elements.
Space Complexity: O(1), since we are not using extra space aside from the result array.
We create two arrays arr1 and arr2 to store the elements of nums. Initially, arr1 contains only nums[0], and arr2 contains only nums[1].
Then we iterate over the elements of nums starting from index 2. If the last element of arr1 is greater than the last element of arr2, we append the current element to arr1; otherwise, we append it to arr2.
Finally, we append the elements of arr2 to arr1 and return arr1.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Approach 1: Using Hash Maps | Time Complexity: O(n + k), where n is the number of elements, and k is the size of the array used as hash map. |
| Approach 2: In-place Marking | Time Complexity: O(n), where n is the number of elements. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Tracking | O(n) | O(n) | Clear and readable implementation when building arrays dynamically |
| In-place Marking | O(n) | O(1) | Memory constrained scenarios or when minimizing auxiliary storage |
3069 Distribute Elements Into Two Arrays I || C++ JAVA PYTHON • Ayush Rao • 509 views views
Watch 9 more video solutions →Practice Distribute Elements Into Two Arrays I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor