Noble integers in an array (count of greater elements is equal to value)

Problem Description

Given an integer array A, find if an integer p exists in the array such that the number of integers greater than p in the array equals to p.

Problem Constraints

$1<=|A|<={10}^6$

$-{10}^9<=Ai<={10}^9$

Input Format

First and only argument is an integer array A.

Output Format

Return 1 if any such integer p is found else return -1.

Example Input

Input 1:
 A = [3, 2, 1, 3]
Input 2:
 A = [1, 1, 3, 3]

Example Output

Output 1:
 1
Output 2:
 -1

Example Explanation

Explanation 1:
 For integer 2, there are 2 greater elements in the array. So, return 1.
Explanation 2:
 There is no such integer exists.

Solution

1. Sort the array A in ascending order. This step takes O(nlogn).
2. Iterate throught the sorted array. Compare the value of index i to the number of elements after index i and check duplicate elements. This step takes O(n).

import Foundation

class Solution {
	func solve(_ A: inout [Int]) -> Int {
        var B = A.sorted()
        
        for i in 0..<(B.count-1) {
            if B[i] == (B.count - 1 - i) && B[i+1] > B[i]{
                return 1
            }
        }
        if B[B.count-1] == 0 {
            return 1
        }
        return -1
	}
}

References

• InterviewBit > Noble Integer
• Noble integers in an array (count of greater elements is equal to value)