I have been struggling to solve an array problem with linear time, The problem is: Assuming we are given an array A [1...n] write an algorithm that return true if: There are two numbers in the array x,y that have the following:

1. x < y
2. x repeats more than n/3 times
3. y repeats more than n/4 times

I have tried to write the following java program to do so assuming we have a sorted array but I don't think it is the best implementation.

    public static boolean solutionManma(){
    int [] arr = {2,2,2,3,3,3};
    int n = arr.length;
    int xCount = 1;
    int yCount = 1;
    int maxXcount= xCount,maxYCount = yCount;
    int currX = arr[0];
    int currY = arr[n-1];

    for(int i = 1; i < n-2;i  ){
        int right = arr[n-2-i 1];
        int left = arr[i];

        if(currX == left){
            xCount  ;
        }
        else{
            maxXcount = Math.max(xCount,maxXcount);
            xCount = 1;
            currX = left;
        }
        if(currY == right){
            yCount  ;
        }
        else {
            maxYCount = Math.max(yCount,maxYCount);
            yCount = 1;
            currY = right;
        }

    }
    return (maxXcount > n/3 && maxYCount > n/4);
}

If anyone has an algorithm idea for this kind of issue (preferably O(n)) I would much appreciate it because I got stuck with this one.

CodePudding user response：

The key part of this problem is to find in linear time and constant space the values which occur more than n/4 times. (Note: the text of your question says "more than" and the title says "at least". Those are not the same condition. This answer is based on the text of your question.)

There are at most three values which occur more than n/4 times, and a list of such values must also include any value which occurs more than n/3 times.

The algorithm we'll use returns a list of up to three values. It only guarantees that all values which satisfy the condition are in the list it returns. The list might include other values, and it does not provide any information about the precise frequencies.

So a second pass is necessary, which scans the vector a second time counting the occurrences of each of the three values returned. Once you have the three counts, it's simple to check whether the smallest value which occurs more than n/3 times (if any) is less than the largest value which occurs more than n/4 times.

To construct the list of candidates, we use a generalisation of the Boyer-Moore majority vote algorithm, which finds a value which occurs more than n/2 times. The generalisation, published in 1982 by J. Misra and D. Gries, uses k-1 counters, each possibly associated with a value, to identify values which might occur more than 1/k times. In this case, k is 4 and so we need three counters.

Initially, all of the counters are 0 and are not associated with any value. Then for each value in the array, we do the following:

• If there is a counter associated with that value, we increment it.
• If no counter is associated with that value but some counter is at 0, we associate that counter with the value and increment its count to 1.
• Otherwise, we decrement every counter's count.

Once all the values have been processed, the values associated with counters with positive counts are the candidate values.

For a general implementation where k is not known in advance, it would be possible to use a hash-table or other key-value map to identify values with counts. But in this case, since it is known that k is a small constant, we can just use a simple vector of three value-count pairs, making this algorithm O(n) time and O(1) space.

CodePudding user response：

You can use IntStream to stream the array, and anyMatch() to check if any value satisfies all the conditions:

public static boolean check(int [] arr) {
    int length = arr.length;
    
    double timesX = length / 3d;
    double timesY = length / 4d;
    
    return IntStream.of(arr).distinct()
            .anyMatch(x -> count(arr, x) > timesX && IntStream.of(arr)
                    .anyMatch(y -> x < y && count(arr, y) > timesY));
}

private static long count(int [] arr, int value) {
    return IntStream.of(arr).filter(i -> i == value).count();
}