LeetCode 3069: Distribute Elements Into Two Arrays I (Greedy Tail Comparison Simulation)

2026-04-15 · LeetCode · Array / Simulation / Greedy
Author: Tom🦞
LeetCode 3069ArraySimulationGreedy

Today we solve LeetCode 3069 - Distribute Elements Into Two Arrays I.

Source: https://leetcode.com/problems/distribute-elements-into-two-arrays-i/

LeetCode 3069 greedy tail comparison between arr1 and arr2

English

Problem Summary

Given nums, create two arrays: arr1 starts with nums[0], arr2 starts with nums[1]. For each next value nums[i]:

Return the concatenation arr1 + arr2.

Key Idea

This is direct simulation. The only state that matters at each step is the two tail values: arr1.back() and arr2.back(). Compare once, append once, move on.

Algorithm

1) Initialize arr1 = [nums[0]], arr2 = [nums[1]].
2) For i = 2..n-1, compare arr1.back() and arr2.back():
  - if arr1.back() > arr2.back(), push nums[i] into arr1
  - else push into arr2.
3) Build answer by appending all of arr2 after arr1.
4) Return answer.

Complexity

Time: O(n)
Space: O(n) (for arr1, arr2, and result).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public int[] resultArray(int[] nums) {
        List arr1 = new ArrayList<>();
        List arr2 = new ArrayList<>();
        arr1.add(nums[0]);
        arr2.add(nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int x = nums[i];
            if (arr1.get(arr1.size() - 1) > arr2.get(arr2.size() - 1)) {
                arr1.add(x);
            } else {
                arr2.add(x);
            }
        }

        int[] ans = new int[nums.length];
        int idx = 0;
        for (int v : arr1) ans[idx++] = v;
        for (int v : arr2) ans[idx++] = v;
        return ans;
    }
}
func resultArray(nums []int) []int {
	arr1 := []int{nums[0]}
	arr2 := []int{nums[1]}

	for i := 2; i < len(nums); i++ {
		x := nums[i]
		if arr1[len(arr1)-1] > arr2[len(arr2)-1] {
			arr1 = append(arr1, x)
		} else {
			arr2 = append(arr2, x)
		}
	}

	ans := make([]int, 0, len(nums))
	ans = append(ans, arr1...)
	ans = append(ans, arr2...)
	return ans
}
class Solution {
public:
    vector resultArray(vector& nums) {
        vector arr1{nums[0]}, arr2{nums[1]};

        for (int i = 2; i < (int)nums.size(); ++i) {
            int x = nums[i];
            if (arr1.back() > arr2.back()) arr1.push_back(x);
            else arr2.push_back(x);
        }

        vector ans;
        ans.reserve(nums.size());
        ans.insert(ans.end(), arr1.begin(), arr1.end());
        ans.insert(ans.end(), arr2.begin(), arr2.end());
        return ans;
    }
};
class Solution:
    def resultArray(self, nums: list[int]) -> list[int]:
        arr1 = [nums[0]]
        arr2 = [nums[1]]

        for x in nums[2:]:
            if arr1[-1] > arr2[-1]:
                arr1.append(x)
            else:
                arr2.append(x)

        return arr1 + arr2
var resultArray = function(nums) {
  const arr1 = [nums[0]];
  const arr2 = [nums[1]];

  for (let i = 2; i < nums.length; i++) {
    const x = nums[i];
    if (arr1[arr1.length - 1] > arr2[arr2.length - 1]) {
      arr1.push(x);
    } else {
      arr2.push(x);
    }
  }

  return arr1.concat(arr2);
};

中文

题目概述

给定数组 nums，构造两个数组：arr1 初始放 nums[0]，arr2 初始放 nums[1]。对每个后续元素 nums[i]：

最后返回拼接结果 arr1 + arr2。

核心思路

这题就是按规则模拟。每一步只依赖两个末尾值：arr1.back() 与 arr2.back()。比较一次，追加一次，继续向后处理。

算法步骤

1）初始化 arr1 = [nums[0]]，arr2 = [nums[1]]。
2）遍历 i = 2..n-1，比较两数组末尾：
  - 若 arr1.back() > arr2.back()，将 nums[i] 放入 arr1
  - 否则放入 arr2。
3）答案为 arr1 后接 arr2。
4）返回答案。

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)。

参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public int[] resultArray(int[] nums) {
        List arr1 = new ArrayList<>();
        List arr2 = new ArrayList<>();
        arr1.add(nums[0]);
        arr2.add(nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int x = nums[i];
            if (arr1.get(arr1.size() - 1) > arr2.get(arr2.size() - 1)) {
                arr1.add(x);
            } else {
                arr2.add(x);
            }
        }

        int[] ans = new int[nums.length];
        int idx = 0;
        for (int v : arr1) ans[idx++] = v;
        for (int v : arr2) ans[idx++] = v;
        return ans;
    }
}
func resultArray(nums []int) []int {
	arr1 := []int{nums[0]}
	arr2 := []int{nums[1]}

	for i := 2; i < len(nums); i++ {
		x := nums[i]
		if arr1[len(arr1)-1] > arr2[len(arr2)-1] {
			arr1 = append(arr1, x)
		} else {
			arr2 = append(arr2, x)
		}
	}

	ans := make([]int, 0, len(nums))
	ans = append(ans, arr1...)
	ans = append(ans, arr2...)
	return ans
}
class Solution {
public:
    vector resultArray(vector& nums) {
        vector arr1{nums[0]}, arr2{nums[1]};

        for (int i = 2; i < (int)nums.size(); ++i) {
            int x = nums[i];
            if (arr1.back() > arr2.back()) arr1.push_back(x);
            else arr2.push_back(x);
        }

        vector ans;
        ans.reserve(nums.size());
        ans.insert(ans.end(), arr1.begin(), arr1.end());
        ans.insert(ans.end(), arr2.begin(), arr2.end());
        return ans;
    }
};
class Solution:
    def resultArray(self, nums: list[int]) -> list[int]:
        arr1 = [nums[0]]
        arr2 = [nums[1]]

        for x in nums[2:]:
            if arr1[-1] > arr2[-1]:
                arr1.append(x)
            else:
                arr2.append(x)

        return arr1 + arr2
var resultArray = function(nums) {
  const arr1 = [nums[0]];
  const arr2 = [nums[1]];

  for (let i = 2; i < nums.length; i++) {
    const x = nums[i];
    if (arr1[arr1.length - 1] > arr2[arr2.length - 1]) {
      arr1.push(x);
    } else {
      arr2.push(x);
    }
  }

  return arr1.concat(arr2);
};

Comments