CODEWITHSUNDEEP
arraysloopsdata-structures
user12707940
user12707940

Reputation: 161

Data Structure Question on Arrays - How to find the best of array given conditions

I am new and learning Data structure and algorithm, I need help to solve this question

The best of an array having N elements is defined as sum of best of all elements of Array. The best of element A[i] is defined in the following manner

a: The best of element A[i] is 1 if, A[i-1]<A[i]<A[i+1]
b: The best of element A[i] is 2 if, A[i]> A[j] for j ranging from 0 to n-1
                                 and A[i]<A[h] for h ranging from i+1 to N-1

Write program to find best of array

Note- A[0] and A[N-1] are excluded to find best of array, all elements are unique

Input - 2,1,3,9,20,7,8

Output - 3

The best of element 3 is 2 and 9 is 1. For rest element it is 0. Hence 2+1 =3

This is what I tried so far -

public static void main (String [] args) {
        
    int [] A = {2,1,3,9,20,7,8};
        
    int result = 0;
                
    for(int i=1; i<A.length-2; i++) {
        if(A[i-1] < A[i] && A[i]< A[i+1] ) {
            result += 1;
        }else if(A[i]>A[j] && A[i]<A[h]){
            result +=2;
        }else {
            result+=0;
        }
    }   
}

Upvotes: 2

Views: 302

Answers (1)

Yahya
Yahya

Reputation: 14102

Note how the phrase:

A[i]> A[j] for j ranging from 0 to n-1

simply means: If the current element is not the Minimum of the array. Hence, if you find the minimum at the beginning, this condition can be changed into a much simpler and lightweight condition:

 Let m be the minimum of the array, then if A[i] > m

So you don't need to do a linear search every iteration --> Less time complexity.

Now you have the problem with a complexity of O(N^2), ..which can be reduced further.

Regarding

and A[i]<A[h] for h ranging from i+1 to N-1

Get the maximum element from 2 to N-1. Then at every iteration, check if the current element is less than the maximum. If so, consider it while composing the score, otherwise, that means the current element is the maximum, in this case, re-calculate the maximum element from i+1 to N-1.

The worst case scenario is to find the maximum is always at index i where the array is already sorted in descending order.

Whereas the best case scenario is if the maximum is always the last element, hence the overall complexity is reduced to O(N).

Regarding

A[i-1]<A[i]<A[i+1]

This is straightforward, you simply compare the elements reside at those three indices at every iteration.

Implementation

Before anything, the following are important notes:

  1. The result you've got in your example isn't correct as elements 3 and 9 both fulfill both conditions, so each should score either 1 or 2, but cannot be one with score of 1 and another with score of 2. Hence the overall score should be either 1+1 = 2 or 2 + 2 = 4.

  2. I implemented this algorithm in Java (although I prefer Python), as I could guess it from your code snippet.

    import java.util.Arrays;

public class ArrayBest {

private static int[] findMinMax(Integer [] B) {
    // find minimum and the maximum: Time Complexity O(n log(n))
    Integer[] b = Arrays.copyOf(B, B.length);
    Arrays.sort(b);
    return new int []{b[0], b[B.length-1]};
}

public static int find(Integer [] A) {
    // Exclude the first and last elements
    int N = A.length;
    Integer [] B = Arrays.copyOfRange(A, 1, N-1);
    N -= 2;

    // find minimum and the maximum: Time Complexity O(n log(n))
    // min at index 0, and max at index 1
    int [] minmax = findMinMax(B);

    int result = 0;

    // start the search
    for (int i=0; i<N-1; i++) {
        // start with first condition : the easier
        if (i!=0 && B[i-1]<B[i] && B[i]<B[i+1]) {
            result += 1;
        }else if (B[i] != minmax[0]) {  // Equivalent to A[i]> A[j] : j in [0, N-1] 
            if (B[i] < minmax[1]) {  // if it is less than the maximum
                result += 2;
            }else { // it is the maximum --> re-calculate the max over the range (i+1, N)
                int [] minmax_ = findMinMax(Arrays.copyOfRange(B, i+1, N));
                minmax[1] = minmax_[1];
            }
        } 
    }
    return result;
}
public static void main(String[] args) {
    Integer [] A = {2,1,3,9,7,20,8};
    int res = ArrayBest.find(A);
    System.out.println(res);
}

}

Ignoring the first sort, the best case scenario is when the last element is the maximum (i.e, at index N-1), hence time complexity is O(N).

The worst case scenario, is when the array is already sorted in a descending order, so the current element that is being processed is always the maximum, hence at each iteration the maximum should be found again. Consequently, the time complexity is O(N^2).

The average case scenario depends on the probability of how the elements are distributed in the array. In other words, the probability that the element being processed at the current iteration is the maximum. Although it requires more study, my initial guess is as follows:

The probability of any i.i.d element to be the maximum is simply 1/N, and that is at the very beginning, but as we are searching over (i+1, N-1), N will be decreasing, hence the probability will go like: 1/N, 1/(N-1), 1/(N-2), ..., 1. Counting the outer loop, we can write the average complexity as O(N (1/N + 1/(N-1), 1/(N-2), + ... +1)) = O(N (1 + 1/2 + 1/3 + ... + 1/N)) where its asymptotic upper bound (according to Harmonic series) is approximately O(N log(N)).

Upvotes: 1

Related Questions