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 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.

Description Solution Video 3:23

4065. Rearrange Array by Removing Distinct Values

Easy75.0% acceptance

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

Topics

3:23

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def rearrangeArray(self, nums: list[int]) -> list[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[3,1,3,2,1,3]

Input

[7,7,4,4,4]

Your code is saved on this device.Solution