problemeasyalgorithmsnoble-integer-in-arraynoble integer in arraynobleintegerinarray

Noble Integer

EasyUpdated: Aug 17, 2025
Practice on:
InterviewBit

Problem

Given an integer array, find if an integer p exists in the array such that the number of integers greater than p in the array equals to p. If such an integer is found return 1 else return -1. Given an integer array, find if there exists an integer p such that the number of integers strictly greater than p in the array is exactly p. If such an integer exists, return 1. Otherwise, return -1.

Examples

Example 1

Input: [3, 2, 1, 3]
Output: 1
Explanation: For p = 2, there are exactly 2 elements greater than 2 (the two 3's).

Example 2

Input: [1, 1, 3, 3]
Output: -1
Explanation: No such integer exists.

Solution

Method 1 – Sorting and Linear Scan

Intuition

If we sort the array, the number of elements greater than a given value is easy to compute as the number of elements to its right. We need to be careful with duplicates: only consider a value if it is the last occurrence of that value in the sorted array.

Approach

  1. Sort the array in non-decreasing order.
  2. For each element (except the last), if it is not equal to the next element and the number of elements to its right equals its value, return 1.
  3. After the loop, check if the last element is 0 (since there are 0 elements greater than it).
  4. If no such element is found, return -1.

Code

C++
class Solution {
public:
	int solve(vector<int> &A) {
		sort(A.begin(), A.end());
		int n = A.size();
		for (int i = 0; i < n - 1; ++i) {
			if (A[i] == A[i+1]) continue;
			if (A[i] == n - i - 1) return 1;
		}
		if (A[n-1] == 0) return 1;
		return -1;
	}
};
Java
class Solution {
	public int solve(int[] A) {
		Arrays.sort(A);
		int n = A.length;
		for (int i = 0; i < n - 1; i++) {
			if (A[i] == A[i+1]) continue;
			if (A[i] == n - i - 1) return 1;
		}
		if (A[n-1] == 0) return 1;
		return -1;
	}
}
Python
from typing import List
class Solution:
	def solve(self, A: List[int]) -> int:
		A.sort()
		n = len(A)
		for i in range(n - 1):
			if A[i] == A[i+1]:
				continue
			if A[i] == n - i - 1:
				return 1
		if A[-1] == 0:
			return 1
		return -1

Complexity

  • ⏰ Time complexity: O(n log n), due to sorting the array of length n.
  • 🧺 Space complexity: O(1), if sorting is done in-place; otherwise O(n) if a new array is created for sorting.

Comments