Data Structures | Problem 1: Arrays | Two Greater Elements

Software Development
#1

Problem Description

You are given an array of distinct integers A, you have to find and return all elements in array which have at-least two greater elements than themselves.

NOTE: The result should have the order in which they are present in the original array.

Problem Constraints

3 <= |A| <= 105

-109 <= A[i] <= 109

Input Format

First and only argument is an integer array A.

Output Format

Return an integer array containing the elements of A which have at-least two greater elements than themselves in A.

Example Input

Input 1:

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

Input 2:

A = [11, 17, 100, 5]

Example Output

Output 1:

[1, 2, 3]

Output 2:

[11, 5]

Example Explanation

Explanation 1:

Number of elements greater than 1: 4 Number of elements greater than 2: 3 Number of elements greater than 3: 2 Number of elements greater than 4: 1 Number of elements greater than 5: 0 Elements 1, 2 and 3 have atleast 2 elements strictly greater than themselves.

Explanation 2:

Number of elements greater than 11: 2 Number of elements greater than 17: 1 Number of elements greater than 100: 0 Number of elements greater than 5: 3 Elements 5 and 11 have atleast 2 elements strictly greater than themselves.

#2

**Here are two solutions in Python for your reference. One is in O(n) and the second one is in O(n*log(n)) **
Solve it in any language of your choice. :slight_smile:

    def solve(A):
        # O(n)
        output = []
        largest = A[0]
        secondLargest = A[1]
        if A[0] > A[1]:
            largest = A[0]
            secondLargest = A[1]
        else:
            largest = A[1]
            secondLargest = A[0]
        for val in A[2:]:
            if val > largest:
                secondLargest = largest;
                largest = val
            elif val < largest and val > secondLargest:
                secondLargest = val
        for val in A:
            if val < largest and val < secondLargest:
                output.append(val)
        return output
                
    # def solve2(A):
    #     # O(n*logn)
    #     output = []
    #     sortedA = A.copy()
    #     sortedA.sort(reverse = True)
    #     for i in A:
    #         if sortedA[0] > i and sortedA[1] > i:
    #             output.append(i)
    #     return output
#3