Python: count number of pairs in array(list) A solution for a small algorithmic problem. I believe tests are pretty descriptive:

def pairs(n):
    return n * (n - 1) / 2

def solution(lst): 
    res = 0
    stack = lst[0:1]
    lst = sorted(lst[1:])
    while(len(lst)):
        nxt = lst.pop()
        if len(stack) and stack[0] == nxt:
            stack.append(nxt)
        else:
            res += pairs(len(stack))
            stack = [nxt]
    else:
        res += pairs(len(stack))
    return res

assert(pairs(3) == 3)
assert(pairs(2) == 1)
assert(pairs(0) == 0)
assert(solution([5, 3, 1, 5, 5, 3]) == 4)
assert(solution([5, 5]) == 1)
assert(solution([5]) == 0)
assert(solution([]) == 0)


UPDATE: there is a bug. I shouldn't take a first element before sorting an array
From what I see you are counting all the pairs of equal numbers that can be formed. (If not, please clarify)

It can be done in another way:


Take the first element of the array.
Count the number of elements equal to it in the array. It can be done via filter, storing the result as a new array, then len.
Call pairs over the length of the filtered array of step 2.
Add the result of pairs to an accumulator (previously initalized at 0).
Repeat steps 2--5 from the next element that is not equal to the one taken previously (for the first iteration, it would be the one taken in step 1). This can be done using filter, then assignment over the original array (if you don't want to preserve it).


The accumulator will be the result.

Quickly tested code snippet:

def countPairs(nums):
    count = 0

    while len(nums):
        probe = nums[0]
        count += pairs(len([x for x in nums if x == probe]))
        nums = [x for x in nums if x != probe]

    return count


EDIT.

Filtering can be thought of as an O(n) operation (iterating and adding elements that fulfill the condition). This is done twice inside the loop. Here, n = len(nums).

On the other hand, the external loop will run as many times as unique(nums), where unique is a function that retrieves the number of unique elements inside the array. Why unique? Because on each iteration, all the elements equal to the probe are taken out of the array (including the probe). They can be 1, 3, all of them. This is done for each iteration.

Nevertheless, unique(nums) &lt;= len(nums), so it can be said the external loop will be a O(n) operation in the worst case.

Therefore, my proposed algorithm runs in O(n^2) time, due to traversing the whole array at most as many times as elements would be in the array.