Skip to content

4065. Rearrange Array by Removing Distinct Values

DifficultyEasy

Description

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

Solutions

Solution 1: Counting

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(\textit{nums})\) and let \(\textit{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 \(\textit{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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
}

Comments