Skip to main content

At Least Two Greater Elements Problem (Geeks for Geeks)

This tutorial contains a complete walk-through of the At Least Two Greater Elements problem from the Geeks for Geeks website. It features the implementation of the solution code in two programming languages: Python and C++.

Problem Description​

Given an array of N distinct elements, the task is to find all elements in array except two greatest elements in sorted order.

Examples​

Example 1:

Input : a[] = {2, 8, 7, 1, 5}
Output : 1 2 5
Explanation : The output three elements have two or more greater elements.

Example 2:

Input : a[] = {7, -2, 3, 4, 9, -1}
Output : -2 -1 3 4

Your Task​

You don't need to read input or print anything. Your task is to complete the function findElements() which takes the array A[] and its size N as inputs and return the vector sorted values denoting the elements in array which have at-least two greater elements than themselves.

Expected Time Complexity: O(N∗Log(N)O(N*Log(N) Expected Auxiliary Space: O(N)O(N)

Constraints​

  • 3 ≤ N ≤ 10^5
  • -10^6 ≤ Ai ≤ 10^6

Problem Explanation​

The problem is to find all elements in an array except the two greatest elements and return them in sorted order. In simpler terms, you want to remove the two largest elements from the array and sort the remaining elements.

Code Implementation​

Written by @iamanolive
class Solution:
def findElements(self, a, n):
a.sort(); return a[0 : -2]

Example Walkthrough​

For the array [2, 8, 7, 1, 5]:

  1. The two greatest elements are 8 and 7.
  2. Removing these two, the remaining elements are [2, 1, 5].
  3. Sorting these remaining elements gives [1, 2, 5].

For the array [7, −2, 3, 4, 9, −1]:

  1. The two greatest elements are 9 and 7
  2. Removing these two, the remaining elements are [−2, 3, 4, −1].
  3. Sorting these remaining elements gives [−2, −1, 3, 4].

Solution Logic:​

  1. Sort the Array: First, sort the entire array.
  2. Remove the Last Two Elements: After sorting, the last two elements will be the greatest. Removing these will leave us with the elements that have at least two greater elements.
  3. Return the Result: The remaining sorted elements are the desired result.

Time Complexity​

  • Sorting the Array: The primary operation is sorting the array, which has a time complexity of O(N∗Log(N)O(N*Log(N), where N is the number of elements in the array.
  • Slicing the Array: Extracting the elements excluding the last two elements has a time complexity of O(1)O(1).

Space Complexity​

Auxiliary Space: The auxiliary space complexity is O(N)O(N) because the sorting algorithm typically requires additional space proportional to the size of the input array.

References​