Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given a 1-indexed array of integers nums of length n.
We define a function greaterCount such that greaterCount(arr, val) returns the number of elements in arr that are strictly greater than val.
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:
greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]), append nums[i] to arr1.greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]), append nums[i] to arr2.greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]), append nums[i] to the array with a lesser number of elements.nums[i] to arr1.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 integer array result.
Example 1:
Input: nums = [2,1,3,3] Output: [2,3,1,3] Explanation: After the first 2 operations, arr1 = [2] and arr2 = [1]. In the 3rd operation, the number of elements greater than 3 is zero in both arrays. Also, the lengths are equal, hence, append nums[3] to arr1. In the 4th operation, the number of elements greater than 3 is zero in both arrays. As the length of arr2 is lesser, hence, append nums[4] to arr2. After 4 operations, arr1 = [2,3] and arr2 = [1,3]. Hence, the array result formed by concatenation is [2,3,1,3].
Example 2:
Input: nums = [5,14,3,1,2] Output: [5,3,1,2,14] Explanation: After the first 2 operations, arr1 = [5] and arr2 = [14]. In the 3rd operation, the number of elements greater than 3 is one in both arrays. Also, the lengths are equal, hence, append nums[3] to arr1. In the 4th operation, the number of elements greater than 1 is greater in arr1 than arr2 (2 > 1). Hence, append nums[4] to arr1. In the 5th operation, the number of elements greater than 2 is greater in arr1 than arr2 (2 > 1). Hence, append nums[5] to arr1. After 5 operations, arr1 = [5,3,1,2] and arr2 = [14]. Hence, the array result formed by concatenation is [5,3,1,2,14].
Example 3:
Input: nums = [3,3,3,3] Output: [3,3,3,3] Explanation: At the end of 4 operations, arr1 = [3,3] and arr2 = [3,3]. Hence, the array result formed by concatenation is [3,3,3,3].
Constraints:
3 <= n <= 1051 <= nums[i] <= 109Problem summary: You are given a 1-indexed array of integers nums of length n. We define a function greaterCount such that greaterCount(arr, val) returns the number of elements in arr that are strictly greater than val. 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 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]), append nums[i] to arr1. If greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]), append nums[i] to arr2. If greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]), append nums[i] to the array with a lesser number of elements. If there is still a tie, append nums[i] to arr1. The array result is formed by concatenating the arrays arr1 and arr2. For example, if arr1 == [1,2,3] and arr2 ==
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Segment Tree
[2,1,3,3]
[5,14,3,1,2]
[3,3,3,3]
split-array-largest-sum)divide-array-into-equal-pairs)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3072: Distribute Elements Into Two Arrays II
class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
this.c = new int[n + 1];
}
public void update(int x, int delta) {
for (; x <= n; x += x & -x) {
c[x] += delta;
}
}
public int query(int x) {
int s = 0;
for (; x > 0; x -= x & -x) {
s += c[x];
}
return s;
}
}
class Solution {
public int[] resultArray(int[] nums) {
int[] st = nums.clone();
Arrays.sort(st);
int n = st.length;
BinaryIndexedTree tree1 = new BinaryIndexedTree(n + 1);
BinaryIndexedTree tree2 = new BinaryIndexedTree(n + 1);
tree1.update(Arrays.binarySearch(st, nums[0]) + 1, 1);
tree2.update(Arrays.binarySearch(st, nums[1]) + 1, 1);
int[] arr1 = new int[n];
int[] arr2 = new int[n];
arr1[0] = nums[0];
arr2[0] = nums[1];
int i = 1, j = 1;
for (int k = 2; k < n; ++k) {
int x = Arrays.binarySearch(st, nums[k]) + 1;
int a = i - tree1.query(x);
int b = j - tree2.query(x);
if (a > b) {
arr1[i++] = nums[k];
tree1.update(x, 1);
} else if (a < b) {
arr2[j++] = nums[k];
tree2.update(x, 1);
} else if (i <= j) {
arr1[i++] = nums[k];
tree1.update(x, 1);
} else {
arr2[j++] = nums[k];
tree2.update(x, 1);
}
}
for (int k = 0; k < j; ++k) {
arr1[i++] = arr2[k];
}
return arr1;
}
}
// Accepted solution for LeetCode #3072: Distribute Elements Into Two Arrays II
type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
return &BinaryIndexedTree{n: n, c: make([]int, n+1)}
}
func (bit *BinaryIndexedTree) update(x, delta int) {
for ; x <= bit.n; x += x & -x {
bit.c[x] += delta
}
}
func (bit *BinaryIndexedTree) query(x int) int {
s := 0
for ; x > 0; x -= x & -x {
s += bit.c[x]
}
return s
}
func resultArray(nums []int) []int {
st := make([]int, len(nums))
copy(st, nums)
sort.Ints(st)
n := len(st)
tree1 := NewBinaryIndexedTree(n + 1)
tree2 := NewBinaryIndexedTree(n + 1)
tree1.update(sort.SearchInts(st, nums[0])+1, 1)
tree2.update(sort.SearchInts(st, nums[1])+1, 1)
arr1 := []int{nums[0]}
arr2 := []int{nums[1]}
for _, x := range nums[2:] {
i := sort.SearchInts(st, x) + 1
a := len(arr1) - tree1.query(i)
b := len(arr2) - tree2.query(i)
if a > b {
arr1 = append(arr1, x)
tree1.update(i, 1)
} else if a < b {
arr2 = append(arr2, x)
tree2.update(i, 1)
} else if len(arr1) <= len(arr2) {
arr1 = append(arr1, x)
tree1.update(i, 1)
} else {
arr2 = append(arr2, x)
tree2.update(i, 1)
}
}
arr1 = append(arr1, arr2...)
return arr1
}
# Accepted solution for LeetCode #3072: Distribute Elements Into Two Arrays II
class BinaryIndexedTree:
__slots__ = "n", "c"
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, delta: int) -> None:
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x: int) -> int:
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def resultArray(self, nums: List[int]) -> List[int]:
st = sorted(set(nums))
m = len(st)
tree1 = BinaryIndexedTree(m + 1)
tree2 = BinaryIndexedTree(m + 1)
tree1.update(bisect_left(st, nums[0]) + 1, 1)
tree2.update(bisect_left(st, nums[1]) + 1, 1)
arr1 = [nums[0]]
arr2 = [nums[1]]
for x in nums[2:]:
i = bisect_left(st, x) + 1
a = len(arr1) - tree1.query(i)
b = len(arr2) - tree2.query(i)
if a > b:
arr1.append(x)
tree1.update(i, 1)
elif a < b:
arr2.append(x)
tree2.update(i, 1)
elif len(arr1) <= len(arr2):
arr1.append(x)
tree1.update(i, 1)
else:
arr2.append(x)
tree2.update(i, 1)
return arr1 + arr2
// Accepted solution for LeetCode #3072: Distribute Elements Into Two Arrays II
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3072: Distribute Elements Into Two Arrays II
// class BinaryIndexedTree {
// private int n;
// private int[] c;
//
// public BinaryIndexedTree(int n) {
// this.n = n;
// this.c = new int[n + 1];
// }
//
// public void update(int x, int delta) {
// for (; x <= n; x += x & -x) {
// c[x] += delta;
// }
// }
//
// public int query(int x) {
// int s = 0;
// for (; x > 0; x -= x & -x) {
// s += c[x];
// }
// return s;
// }
// }
//
// class Solution {
// public int[] resultArray(int[] nums) {
// int[] st = nums.clone();
// Arrays.sort(st);
// int n = st.length;
// BinaryIndexedTree tree1 = new BinaryIndexedTree(n + 1);
// BinaryIndexedTree tree2 = new BinaryIndexedTree(n + 1);
// tree1.update(Arrays.binarySearch(st, nums[0]) + 1, 1);
// tree2.update(Arrays.binarySearch(st, nums[1]) + 1, 1);
// int[] arr1 = new int[n];
// int[] arr2 = new int[n];
// arr1[0] = nums[0];
// arr2[0] = nums[1];
// int i = 1, j = 1;
// for (int k = 2; k < n; ++k) {
// int x = Arrays.binarySearch(st, nums[k]) + 1;
// int a = i - tree1.query(x);
// int b = j - tree2.query(x);
// if (a > b) {
// arr1[i++] = nums[k];
// tree1.update(x, 1);
// } else if (a < b) {
// arr2[j++] = nums[k];
// tree2.update(x, 1);
// } else if (i <= j) {
// arr1[i++] = nums[k];
// tree1.update(x, 1);
// } else {
// arr2[j++] = nums[k];
// tree2.update(x, 1);
// }
// }
// for (int k = 0; k < j; ++k) {
// arr1[i++] = arr2[k];
// }
// return arr1;
// }
// }
// Accepted solution for LeetCode #3072: Distribute Elements Into Two Arrays II
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x: number, delta: number): void {
for (; x <= this.n; x += x & -x) {
this.c[x] += delta;
}
}
query(x: number): number {
let s = 0;
for (; x > 0; x -= x & -x) {
s += this.c[x];
}
return s;
}
}
function resultArray(nums: number[]): number[] {
const st: number[] = nums.slice().sort((a, b) => a - b);
const n: number = st.length;
const search = (x: number): number => {
let [l, r] = [0, n];
while (l < r) {
const mid = (l + r) >> 1;
if (st[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
const tree1: BinaryIndexedTree = new BinaryIndexedTree(n + 1);
const tree2: BinaryIndexedTree = new BinaryIndexedTree(n + 1);
tree1.update(search(nums[0]) + 1, 1);
tree2.update(search(nums[1]) + 1, 1);
const arr1: number[] = [nums[0]];
const arr2: number[] = [nums[1]];
for (const x of nums.slice(2)) {
const i: number = search(x) + 1;
const a: number = arr1.length - tree1.query(i);
const b: number = arr2.length - tree2.query(i);
if (a > b) {
arr1.push(x);
tree1.update(i, 1);
} else if (a < b) {
arr2.push(x);
tree2.update(i, 1);
} else if (arr1.length <= arr2.length) {
arr1.push(x);
tree1.update(i, 1);
} else {
arr2.push(x);
tree2.update(i, 1);
}
}
return arr1.concat(arr2);
}
Use this to step through a reusable interview workflow for this problem.
For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.
Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.