ArraysSortingMedium

Noble Integer

Count elements where the number of elements strictly less than A[i] equals A[i].

Brute: O(N²)Optimal: O(N log N)Space: O(1)

What is it?

An element A[i] is Noble if count( x ∈ A where x < A[i] ) == A[i].

💡

Condition: count( x where x < A[i] ) == A[i]

Full Example

Input

A = [1, -5, 3, 5, 5, -10, 4]     n = 7

A[i]   Elements strictly < A[i]               count   Noble?
─────────────────────────────────────────────────────────────
  1    {{-5, -10}}                             2       2==1?   NO
 -5    {{-10}}                                 1       1==-5?  NO
  3    {{1, -5, -10}}                          3       3==3?   YES ✓
  5    {{1, -5, 3, -10, 4}}                    5       5==5?   YES ✓
  5    {{1, -5, 3, -10, 4}}                    5       5==5?   YES ✓
-10    {{}}                                    0       0==-10? NO
  4    {{1, -5, 3, -10}}                       4       4==4?   YES ✓

✓

Answer = 4. Noble elements: 3, 5, 5, 4

Key Observations

Negatives never Noble — count ≥ 0 always.
Large values can't be Noble — max count = n−1.
Duplicates share the same count — whole array, not position.

→

Noble elements must have value between 0 and n−1.

Brute Force — O(N²)

Java

public int nobleIntegerBrute(int[] A) {{
    int ans = 0, n = A.length;
    for (int i = 0; i < n; i++) {{
        int count = 0;
        for (int j = 0; j < n; j++)
            if (A[j] < A[i]) count++;
        if (count == A[i]) ans++;
    }}
    return ans;
}}

Dry run

i=0  A[i]=1    count=2        2==1?   NO
i=1  A[i]=-5   count=1        1==-5?  NO
i=2  A[i]=3    count=3        3==3?   YES  ans=1
i=3  A[i]=5    count=5        5==5?   YES  ans=2
i=4  A[i]=5    count=5        5==5?   YES  ans=3
i=5  A[i]=-10  count=0        0==-10? NO
i=6  A[i]=4    count=4        4==4?   YES  ans=4
ans = 4  ✓

Optimised — O(N log N)

After sorting ascending, element at index i has exactly i elements strictly smaller (no duplicates). Freeze count at first occurrence of each value:

Key Logic

if (i > 0 && A[i] != A[i - 1]) count = i;  // update at new value
if (count == A[i]) ans++;                        // check every element

Dry Run — Optimised

Trace

Sorted:  [ -10,  -5,   1,   3,   4,   5,   5 ]
index:      0    1    2    3    4    5    6

count=0, ans=0

i=0  A=-10  i==0, no update     count=0  0==-10? NO
i=1  A=-5   new → count=1       count=1  1==-5?  NO
i=2  A=1    new → count=2       count=2  2==1?   NO
i=3  A=3    new → count=3       count=3  3==3?   YES  ans=1
i=4  A=4    new → count=4       count=4  4==4?   YES  ans=2
i=5  A=5    new → count=5       count=5  5==5?   YES  ans=3
i=6  A=5    SAME, no update     count=5  5==5?   YES  ans=4

Final ans = 4  ✓

Final Code

Java

import java.util.Arrays;

public int nobleInteger(int[] A) {{
    Arrays.sort(A);
    int n = A.length, ans = 0, count = 0;

    for (int i = 0; i < n; i++) {{
        if (i > 0 && A[i] != A[i - 1])
            count = i;     // freeze at first occurrence
        if (count == A[i])
            ans++;
    }}
    return ans;
}}

TC: O(N log N)SC: O(1)

✓

Key insight: Sort makes index = count of strictly smaller. Freeze count at first occurrence of each value.

Summary

Approach	Time	Space	Idea
Brute Force	`O(N²)`	`O(1)`	Nested loop
Optimised	`O(N log N)`	`O(1)`	Sort + index trick

← Previous

Comparator & Comparable

Min Cost Removal