We can do it in time O(n) space O(k) with k = number of distinct colors.
function sockMerchant(n, array) {
let count = 0;
const seen = {};
array.forEach((item) => {
if (seen[item]) { // one sock of this color was seen before, so this completes a pair
seen[item] = false;
count++;
} else { // this is the one in a pair
seen[item] = true;
}
});
return count;
}
We can do it in time O(n) space O(k) with k = number of distinct colors.
Great idea. This is a definitely better solution than mine. Thank you for sharing.