Test your understanding of various coding challenges focusing on algorithm efficiency.

Coding

Challenge Yourself

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral

# Statement

For a given array of integers, `nums`, return TRUE if it contains duplicates. Otherwise, return FALSE.

**Constraints:**

* $1 \leq$ `nums.length` $\leq 10^5$

* $-10^9 \leq$ `nums[i]` $\leq 10^9$

# Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time and any implementation constraints.

## Naive approach
The first solution that comes to mind while looking at this problem would be to iterate over all the elements of the `nums` array and compare each element with $(i-1)$ elements to check whether it is repeating. In this way, we will be able to find out if there are repeating duplicate numbers in the array. However, it is an expensive solution in terms of time complexity, since it comes out to be $O(n^2)$.


This can be improved in terms of time complexity. Let's try to devise an optimized solution.


## Optimized approach using knowing what to track
An efficient approach would be to keep track of numbers while iterating over `nums`. This way, we can find out if an element is repeating by just checking its occurrence instead of checking all the rest of the numbers in `nums`. 

To achieve this, we will be using the hash map data structure `records` that is appropriate for problems like this. We iterate over the `nums` array, and for each number, we check if it exists in `records` or not. If it exists, then it means that the number is being repeated and the given array `nums` contains duplicates hence we return TRUE. If it is not the case, we add the current number to the `records` and move to the next number.

If all the numbers have been processed and we haven't encountered any duplicates, we return FALSE, meaning that there is no duplicate in the given `nums` array. 

Let's look at the illustration below to better understand the solution.

Let's solve the Contains Duplicate problem using the Knowing What To Track pattern.

Solution: Contains Duplicate

Statement▼

Solution: Contains Duplicate

Statement▼