Find a number which equals to the total number of integers greater than itself in an array

Question

I am solving interview questions from here.

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

Approach First remove all the negative numbers from the given array and then sort it. Now from the sorted array check for the given condition.

How can I optimize my solution :

def solve(A):
    p = -1
    sum_ind = 0
    sub_array = [x for x in A if x>=0]
    sub_array.sort()
    print sub_array
    for i in range(len(sub_array)):
        for j in range(i+1,len(sub_array)):

            if sub_array[j] > sub_array[i]:
                sum_ind += 1

        if sub_array[i] == sum_ind:
            p = 1
            break
        else:
            sum_ind = 0

    return p

Test Cases:

print solve([ ]) == (-1)
print solve([ -1, -2, 0, 0, 0, -3 ]) == (1)
print solve([4,7,8,9,11]) == (1)
print solve([-4, -2, 0, -1, -6 ]) == (1)
print solve([-4, -2, -1, -6 ]) == (-1) 
print solve([6,7,5 ]) == (-1)
print solve([ 4, -9, 8, 5, -1, 7, 5, 3 ]) == (1)

Answer 1

Let's re-think the problem a little. Let's start as you suggest, by discarding negative values and sorting the array (I'm going to use descending order):

A = sorted([x for x in A if x >= 0], reverse=True)

Now that we have all positive values in descending order, we find a really simple solution to this problem: if any value equals its own index in the array (which is equivalent to how many values are greater than it in the array), then we return 1:

return 1 if any(v == i for i, v in enumerate(A)) else -1

You can see this if you consider a sample array--I'll borrow your example--such as [4,7,8,9,11]. Once sorted in descending order, we can pair each value with its index to get [(0, 11), (1, 9), (2, 8), (3, 7), (4, 4)]. Because of the sorting, the index will always represent the number of values in the array greater than the value at that index.

The exception to this trend is when you have multiple, equal integers, in which case we need to modify this list to not keep incrementing when iterating across duplicate values. E.g., for A = [3, 3, 3, 3, 2, 1], we need the resulting list to be [(0, 3), (0, 3), (0, 3), (0, 3), (4, 2), (5, 1)]. You can solve this using a list that retroactively fixes the enumerated list:

for i, v in A[1:]:
    if v == A[i-1][1]:
        A[i][0] = A[i-1][0]

The final function looks like the following:

def solve(A):
    A = sorted([x for x in A if x >= 0], reverse=True)
    A = list(map(list, enumerate(A)))
    for i, v in A[1:]:
        if v == A[i-1][1]:
            A[i][0] = A[i-1][0]
    return 1 if any(v == i for i, v in A) else -1