Need help with 6-1 variant

#1

Here is the problem:
Given an array A of n objects with keys that take one of four values,
reorder the array so that all objects with the same key appear together.
O(1) additional space and O(n) time

0 Likes
#2

I think I got it myself. How can I delet the post?

0 Likes
#3

How about you share you’re thoughts here?

0 Likes
#4

OK

public static void reorderFourKeys(int pivotIndex1, int pivotIndex2, List<KeyValue> A) {
        if (A == null || A.size() == 0) {
            return;
        }

        Integer pivot1 = (int)A.get(pivotIndex1).key;
        Integer pivot2 = (int)A.get(pivotIndex2).key;
        int smaller = 0, equal = 0, larger = A.size();
        reorderThreeKeys(A, pivot1, smaller, equal, larger);

        smaller = equal;
        larger = A.size();
        reorderThreeKeys(A, pivot2, smaller, equal, larger);
    }

private static void reorderThreeKeys(List<KeyValue> A, Integer pivot, int smaller, int equal, int larger) {
        while (equal < larger) {
            if ((int)A.get(equal).key < pivot) {
                Collections.swap(A, smaller++, equal++);
            } else if ((int)A.get(equal).key == pivot) {
                ++equal;
            } else {
                Collections.swap(A, equal, --larger);
            }
        }
    }
0 Likes
#5

Hey @yxfabroad,

Very good idea that reuse the reorderThreeKeys() function, originally my idea would be solve reorderFourKeys by modifying reorderThreeKeys() with more state variables (to record where each number shall start), but it requires more codes and probably error prone as well. I like your idea to reduce this problem into two times previous solution, which is what we want for variant for sure.

0 Likes