CODEWITHSUNDEEP
arraysalgorithm
Brandon
Brandon

Reputation: 1027

Reordering an array s.t. there are no duplicates in a group

So I'm trying to work through the following interview question:

/** Given an unordered array of positive integers, create an algorithm that makes sure
no group of integers of size bigger than M have the same integers. 

Input: 2,1,1,1,3,4,4,4,5 M = 2 
Output: 2,1,1,3,1,4,4,5,4
*/

I've thought of a O(n^2) solution: iterate through the array and swap adjacent items that are repeats in a given group. But because you have the case like 1,2,3,4,1,1 M = 2 you'd have to wrap around the back of the array potentially n times, giving you the polynomial time.

So I've though of the following solution, which is supposed to run in linear time:

public static int[] regroup(int[] input, int m) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i : input) {
        if (!map.containsKey(i)) {
            map.put(i, 1);
        } else {
            map.put(i, map.get(i) + 1);
        }
    }
    int i = 0, n = 0;
    while (i < input.length) {
        for (int curr : map.keySet()) {
           if (n == m) { 
               n = 0;
               break;
           }
           if (map.get(curr) > 0) {
               input[i] = curr;
               map.put(curr, map.get(curr) - 1);
               i++; n++;
           } else {
               continue;
           }
        }     
    }
    return input;
}

This essentially makes hashmap with all the values to their # of occurrences, then picks one item from each bucket for each M-sized group, guaranteeing unique items. Although the problem I have run into is the following counterexample:

{2,1,1,1,3,4,4,4,5} M = 3

This returns 

[1, 2, 3, 1, 4, 5, 1, 4, 4]

Which clearly isn't right. What happened is that is ran out of unique items to pick from at the end, so just put 4 twice into that last group. Can anyone think of a way to solve this issues and preserve the linear time?

Upvotes: 1

Views: 299

Answers (1)

GOPAL GUPTA
GOPAL GUPTA

Reputation: 27

Once you have counted all element then put them into a heap (number, count). take a pair from heap and start distributing them in input array with difference of M until you reach end of input array. Once you reach end of array then start with next position from previous start of the array. code snippet is given below:

     int curr = 0;
     int start = curr;
     while(maxHeap.size() > 0){
            Pair p = maxHeap.poll();
            int i =0;
            while(i < p.count){
                input[start] = p.num;
// keep putting element at gap of m
                start = start + m;
// if exceeded the length of input array , wrap around with previous start +1.
                if(start >= input.length){
                    curr++;
                    start = current;
                }
                i++;
            }
        }
        return true;
    }

Upvotes: 1

Related Questions