Optimize Duplicate Detection in Arrays

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Optimize Duplicate Detection in Arrays. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

At Stripe, a service receives a list of integer event IDs and needs to quickly determine whether any ID appears more than once. A naive solution compares every pair of elements, but this is too slow for large inputs. Write an optimized algorithm to detect duplicates.

Formal Specification

Implement a function contains_duplicate(nums) that takes a list of integers nums and returns a boolean:

True if any value appears at least twice
False if all values are distinct

Constraints

1 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9
Input contains integers only
Target solution should improve on O(n^2) brute force

Function Signature

def contains_duplicate(nums):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output