4065. Rearrange Array by Removing Distinct Values

The problem

You are given an integer array nums.

You start with an empty array ans. Repeat the following operation until nums is empty:

Identify all distinct values currently present in nums.
Remove one occurrence of every distinct value currently in nums, and append those values to ans in ascending order.

Return the array ans.

Example 1:

Input: nums = [3,1,3,2,1,3]

Output: [1,2,3,1,3,3]

Explanation:

Operation	Appended to `ans`	`nums` after	`ans` after
1	1, 2, 3	`[3, 1, 3]`	`[1, 2, 3]`
2	1, 3	`[3]`	`[1, 2, 3, 1, 3]`
3	3	`[]`	`[1, 2, 3, 1, 3, 3]`

nums is now empty, so the answer is [1, 2, 3, 1, 3, 3].

Example 2:

Input: nums = [7,7,4,4,4]

Output: [4,7,4,7,4]

Explanation:

Operation	Appended to `ans`	`nums` after	`ans` after
1	4, 7	`[7, 4, 4]`	`[4, 7]`
2	4, 7	`[4]`	`[4, 7, 4, 7]`
3	4	`[]`	`[4, 7, 4, 7, 4]`

nums is now empty, so the answer is [4, 7, 4, 7, 4].

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Approach overview

Problem Overview: You get an integer array and need to rearrange it by repeatedly removing its distinct values. Each round targets the values that still have remaining copies, so the answer depends on how often each value appears.

Approach 1: Brute Force Rescan (O(n^2) time, O(n) space)

Start with the full array. In each round, build a set of the values still present, record or remove those values, and rebuild the array from what is left. You repeat until the array is empty. Each round costs a full pass, and the number of rounds can approach n in the worst case, which gives O(n^2) time. This version is easy to reason about because it mirrors the statement directly, so use it to confirm your understanding before optimizing.

Approach 2: Counting with a Frequency Map (O(n) time, O(n) space)

Count how many times each value appears with a Counter, HashMap, or unordered_map. The key insight is that a value's count tells you exactly how many rounds it survives. Once you know each count, you can group values by how many rounds they participate in and build the result in one pass over the counts instead of re-simulating. Every element is touched a constant number of times, so total time is O(n). Extra space is O(n) for the map in the worst case where all values are distinct. Prefer this approach whenever the statement involves repeated removal, because it turns a simulation into arithmetic on counts.

Approach 3: Sorting Plus Grouping (O(n log n) time, O(n) space)

Sort the array so equal values sit next to each other, then scan runs of equal elements to get their multiplicities. This gives the same information as a frequency map without hashing. It is useful when you want deterministic ordering of values or when hashing is undesirable, but it adds a log factor that the counting method avoids. Heaps or ordered sets can also track multiplicities, though they add overhead with no benefit for this problem.

Recommended for interviews: Interviewers expect you to start with the rescan simulation to show you understand the removal rule. The frequency-count solution shows you can see the structure in the problem and remove the repeated work. Explain the O(n^2) version first, state why it is slow, then move to counting. Mention the sorting alternative only if asked about trade-offs.

Related topics: hash table, counting, sorting.

Solution

Thinking

Both n and every value are at most 100, so taking one copy of each remaining value per round fits the limits. Each round has to collect the values still present and delete one of each in ascending order. Searching and deleting inside the original array keeps moving the indices.

A value is emitted once for every time it occurs, and the order inside a round depends only on the value, not on its original index.

Count by value. The range is [1,m]. Scan from small to large, and while a count is still positive, append that value and decrease the count. Repeat until the answer has length n. Each scan is one operation.

Let m=max(nums) and let cnt[x] be the number of times x occurs. Round k, starting from 0, appends every value that still remains, in ascending order. Those are exactly the values whose original frequency is greater than k.

Store the frequencies in an array of length m+1. While the answer has fewer than n elements, scan x from 1 to m. If cnt[x]>0, append x and decrease the count. One scan is one operation, and the appended values are already sorted.

The time complexity is O(nm) and the space complexity is O(m).

Python

class Solution:
    def rearrangeArray(self, nums: list[int]) -> list[int]:
        mx = max(nums)
        cnt = [0] * (mx + 1)
        for x in nums:
            cnt[x] += 1

        ans = []
        while len(ans) < len(nums):
            for x in range(1, mx + 1):
                if cnt[x]:
                    ans.append(x)
                    cnt[x] -= 1
        return ans

Java

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }
        int[] cnt = new int[mx + 1];
        for (int x : nums) {
            cnt[x]++;
        }

        int[] ans = new int[nums.length];
        int idx = 0;
        while (idx < nums.length) {
            for (int x = 1; x <= mx; x++) {
                if (cnt[x] > 0) {
                    ans[idx++] = x;
                    cnt[x]--;
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        int mx = ranges::max(nums);
        vector<int> cnt(mx + 1);
        for (int x : nums) {
            cnt[x]++;
        }

        vector<int> ans;
        while (ans.size() < nums.size()) {
            for (int x = 1; x <= mx; x++) {
                if (cnt[x]) {
                    ans.push_back(x);
                    cnt[x]--;
                }
            }
        }
        return ans;
    }
};

TypeScript

function rearrangeArray(nums: number[]): number[] {
    const mx = Math.max(...nums);
    const cnt = new Array(mx + 1).fill(0);

    for (const x of nums) {
        cnt[x]++;
    }

    const ans: number[] = [];
    while (ans.length < nums.length) {
        for (let x = 1; x <= mx; x++) {
            if (cnt[x]) {
                ans.push(x);
                cnt[x]--;
            }
        }
    }
    return ans;
}

func rearrangeArray(nums []int) []int {
	mx := slices.Max(nums)

	cnt := make([]int, mx+1)
	for _, x := range nums {
		cnt[x]++
	}

	ans := make([]int, 0, len(nums))
	for len(ans) < len(nums) {
		for x := 1; x <= mx; x++ {
			if cnt[x] > 0 {
				ans = append(ans, x)
				cnt[x]--
			}
		}
	}
	return ans
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Rescan	O(n^2)	O(n)	Small inputs or verifying the rule
Counting with Frequency Map	O(n)	O(n)	General case and interviews
Sorting Plus Grouping	O(n log n)	O(n)	When hashing is not allowed or sorted output is needed

Frequently asked questions

Is Rearrange Array by Removing Distinct Values easy or hard?

It is rated Easy with a 74.4% acceptance rate. The difficulty comes from recognizing that a frequency count replaces the repeated simulation, so once you see that, the implementation is short.

How to solve Rearrange Array by Removing Distinct Values in O(n)?

Build a frequency map of the array, then use the counts to determine each value's removal pattern without rescanning. Each element is visited a constant number of times, so the total work stays linear.

Rearrange Array by Removing Distinct Values Python or Java solution?

In Python, use collections.Counter to get frequencies in one pass. In Java, use a HashMap<Integer, Integer> to count occurrences. Both run in O(n) time and O(n) space, and FleetCode provides counting solutions in Python, Java, C++, Go, and TypeScript.

What is the best approach for Rearrange Array by Removing Distinct Values?

The best approach is counting with a frequency map. Count each value's occurrences in one pass, then derive the result from the counts instead of re-simulating removals. This runs in O(n) time with O(n) extra space.

What data structure is used in Rearrange Array by Removing Distinct Values?

The main data structure is a hash map (dictionary or counter) that stores each value's frequency. Sorting or an ordered set can also work, but they add a log factor that the hash map avoids.

What is the time complexity of Rearrange Array by Removing Distinct Values?

The optimal solution runs in O(n) time because each element is counted once and the counts are processed in linear time. A naive simulation that rescans the array every round takes O(n^2) time.

Is Rearrange Array by Removing Distinct Values asked at Google, Amazon, or Meta?

Company-specific frequency data for this problem is not confirmed on FleetCode. Check recent reported question lists for your target company, and expect it to appear as an easy warm-up on array and hash table questions.

Rearrange Array by Removing Distinct Values solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Rearrange Array by Removing Distinct Values solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems