Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Distribute Elements Into Two Arrays I solution and explanation

EasyArraySimulation5 min read83.4% acceptanceUpdated 9 Apr 2026
Asked atAutodeskAmazon
Practise Distribute Elements Into Two Arrays I
1:31
100243 Distribute Elements Into Two Arrays I | leetcode | contest 387 | solved | java | solvedSsquare · 1:31 · 1K viewsWatch on YouTube
9 more videos on this problem
  1. 100243 Distribute Elements Into Two Arrays I | leetcode | contest 387 | solved | java | solvedSsquare · 1:31 · 1K views
  2. 3069 Distribute Elements Into Two Arrays I || C++ JAVA PYTHONAyush Rao · 3:55 · 514 views
  3. 3069. Distribute Elements Into Two Arrays I | LeetCode Weekly Contest 387 | C++Priyanshi Porwal · 6:16 · 272 views
  4. 3069. Distribute Elements Into Two Arrays I (Leetcode Easy)Programming Live with Larry · 2:57 · 232 views
  5. #LeetCode 3069 | Distribute Elements Into Two Arrays I #JavaSleepy Cracker · 4:46 · 188 views
  6. Leetcode # 3069 Distribute Elements Into Two Arrays I (Python)Sumanshu Nankana · 8:29 · 122 views
  7. LeetCode: 3069. Distribute Elements Into Two Arrays I | Day 21CodeWithMaaz · 10:25 · 117 views
  8. LeetCode | 3069. Distribute Elements Into Two Arrays I | Weekly Contest 387Coding with Bobby · 1:52 · 77 views
  9. Leetcode Q.3069 Distribute Elements Into Two Arrays I | PythonCodingOP · 5:45 · 56 views
  10. Python : Distribute Elements Into Two ArraysGrow with Data · 16:51 · 104 views

The problem

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.

Approach overview

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.

Approach 1: Approach 1: Using Hash Maps

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.

def find_duplicates(nums):
    freq_map = {}
    result = []
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1
    for num, count in freq_map.items():
        if count > 1:
            result.append(num)
    return result
import java.util.*;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> result = new LinkedList<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) {
                result.add(entry.getKey());
            }
        }
        return result;
    }
}
#include <iostream>
#include <unordered_map>
#include <vector>

std::vector<int> findDuplicates(const std::vector<int>& nums) {
    std::unordered_map<int, int> map;
    std::vector<int> result;
    for (int num : nums) {
        map[num]++;
    }
    for (auto& pair : map) {
        if (pair.second > 1) {
            result.push_back(pair.first);
        }
    }
    return result;
}
function findDuplicates(nums) {
    const freqMap = new Map();
    const result = [];
    for (let num of nums) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }
    for (let [num, count] of freqMap.entries()) {
        if (count > 1) {
            result.push(num);
        }
    }
    return result;
}
#include <stdio.h>
#include <stdlib.h>

#define SIZE 100

int* findDuplicates(int* nums, int numsSize, int* returnSize) {
    int* map = (int*)calloc(SIZE, sizeof(int));
    int* result = (int*)malloc(numsSize * sizeof(int));
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        map[nums[i]]++;
    }
    for (int i = 0; i < SIZE; i++) {
        if (map[i] > 1) {
            result[count++] = i;
        }
    }
    *returnSize = count;
    free(map);
    return result;
}
using System;
using System.Collections.Generic;

class Solution {
    public IList<int> FindDuplicates(int[] nums) {
        Dictionary<int, int> map = new Dictionary<int, int>();
        List<int> result = new List<int>();
        foreach (int num in nums) {
            if (map.ContainsKey(num)) {
                map[num]++;
            } else {
                map[num] = 1;
            }
        }
        foreach (var entry in map) {
            if (entry.Value > 1) {
                result.Add(entry.Key);
            }
        }
        return result;
    }
}

This Python solution utilizes a dictionary to keep a count of each element's occurrence. Elements that have a frequency greater than 1 are added to the result list.

Complexity

Time Complexity: O(n), where n is the number of elements.
Space Complexity: O(n), for storing elements in the dictionary.

Try this approach in the editor

Approach 2: Approach 2: In-place Marking

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.

def find_duplicates(nums):
    result = []
    for num in nums:
        index = abs(num) - 1
        if nums[index] < 0:
            result.append(abs(num))
        else:
            nums[index] = -nums[index]
    return result
import java.util.*;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] < 0) {
                result.add(Math.abs(nums[i]));
            } else {
                nums[index] = -nums[index];
            }
        }
        return result;
    }
}
#include <iostream>
#include <vector>

std::vector<int> findDuplicates(std::vector<int>& nums) {
    std::vector<int> result;
    for (int i = 0; i < nums.size(); ++i) {
        int index = abs(nums[i]) - 1;
        if (nums[index] < 0) {
            result.push_back(abs(nums[i]));
        } else {
            nums[index] = -nums[index];
        }
    }
    return result;
}
function findDuplicates(nums) {
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        const index = Math.abs(nums[i]) - 1;
        if (nums[index] < 0) {
            result.push(Math.abs(nums[i]));
        } else {
            nums[index] = -nums[index];
        }
    }
    return result;
}
#include <stdio.h>
#include <stdlib.h>

#define ABS(x) ((x) < 0 ? -(x) : (x))

int* findDuplicates(int* nums, int numsSize, int* returnSize) {
    int* result = (int*)malloc(numsSize * sizeof(int));
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        int index = ABS(nums[i]) - 1;
        if (nums[index] < 0) {
            result[count++] = ABS(nums[i]);
        } else {
            nums[index] = -nums[index];
        }
    }
    *returnSize = count;
    return result;
}
using System;
using System.Collections.Generic;

class Solution {
    public IList<int> FindDuplicates(int[] nums) {
        List<int> result = new List<int>();
        for (int i = 0; i < nums.Length; i++) {
            int index = Math.Abs(nums[i]) - 1;
            if (nums[index] < 0) {
                result.Add(Math.Abs(nums[i]));
            } else {
                nums[index] = -nums[index];
            }
        }
        return result;
    }
}

The Python solution uses in-place negation to detect duplicates. By modifying the input list, it keeps track of seen elements and marks duplicates effectively.

Complexity

Time Complexity: O(n), where n is the number of elements.
Space Complexity: O(1), since input list is utilized for marking.

Try this approach in the editor

Approach 3: Simulation

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.

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);
}
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...)
}
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
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Using Hash Maps

Time Complexity: O(n), where n is the number of elements.
Space Complexity: O(n), for storing elements in the dictionary.

Approach 2: In-place Marking

Time Complexity: O(n), where n is the number of elements.
Space Complexity: O(1), since input list is utilized for marking.

Simulation–

Complexity analysis

ApproachTimeSpaceWhen to Use
Hash Map TrackingO(n)O(n)Clear and readable implementation when building arrays dynamically
In-place MarkingO(n)O(1)Memory constrained scenarios or when minimizing auxiliary storage

Frequently asked questions

Is Distribute Elements Into Two Arrays I easy or hard?

Distribute Elements Into Two Arrays I is classified as an Easy problem. The main challenge is correctly following the rule that compares the last elements of the two arrays. Once the simulation logic is implemented, the algorithm runs in linear time with straightforward code.

Distribute Elements Into Two Arrays I Python/Java solution

In Python or Java, create two lists or ArrayLists and initialize them with the first two elements. Iterate through the rest of nums, compare the last values using arr1[-1] and arr2[-1] (or get(size-1) in Java), append the element to the appropriate list, and finally merge the lists into the output array.

How to solve Distribute Elements Into Two Arrays I in O(n)?

Start arr1 with nums[0] and arr2 with nums[1]. Traverse the array from index 2 onward. Compare the last element of arr1 and arr2; append the current number to arr1 if its last value is larger, otherwise append it to arr2. After finishing the traversal, return the concatenation of arr1 followed by arr2.

What is the best approach for Distribute Elements Into Two Arrays I?

The best approach is a direct simulation using two arrays and comparing their last elements at each step. Iterate through the input once, append the current element to arr1 or arr2 depending on which array has the larger last value, and finally concatenate both arrays. This solution runs in O(n) time and uses O(n) space for the resulting arrays.

Is Distribute Elements Into Two Arrays I asked at Google/Amazon/Meta?

Problems of this style appear frequently in screening rounds at companies like Amazon and Google because they test basic array manipulation and careful implementation of rules. While this exact problem may not always appear, similar simulation and array distribution tasks are common in interviews.

What data structure is used in Distribute Elements Into Two Arrays I?

The primary data structure is a dynamic array or list to store arr1 and arr2 as elements are appended. Some implementations also use a small hash map to track the latest values of each array, but the core idea relies on simple array operations and comparisons.

What is the time complexity of Distribute Elements Into Two Arrays I?

The time complexity is O(n) because each element in the input array is processed exactly once. Every step performs a constant-time comparison and append operation. The space complexity is O(n) since two arrays are built to store the distributed elements.

Comments

Next problem · similarSplit Array Largest SumHard
Now write it yourselfClose this page and solve Distribute Elements Into Two Arrays I in the editor, without looking.
Practise Distribute Elements Into Two Arrays I