All problems

Matching Sock Pairs

Easy · hash map

After a big wash, Theo tips a basket of socks onto the floor. The list socks gives the colour code of each sock, in the order he picked them up. Socks of the same colour look identical.

A match is a choice of two different socks, at positions i and j with i < j, that have the same colour. The order inside a match does not matter, so positions 2 and 5 are one match, not two.

Return the total number of matches.

For example, if three socks share a colour, they make 3 matches between them: first and second, first and third, second and third.

Examples

Example 1

Input: socks = [1, 2, 1, 1, 2]

Output: 4

Colour 1 sits at positions 0, 2 and 3, which gives 3 matches. Colour 2 sits at positions 1 and 4, which gives 1 match.

Example 2

Input: socks = [5, 6, 7]

Output: 0

No two socks share a colour.

Example 3

Input: socks = [4, 4]

Output: 1

Constraints