219. Contains Duplicate II
Contains Duplicate II (LeetCode 219) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
How to solve Contains Duplicate II
Contains Duplicate II is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.
Work towards the solution in these steps:
- Think about how you can efficiently check for duplicates within a window of size k as you iterate through the array.
- A hash map (dictionary) can help you track the last seen index of each number.
- For each element, check if it has appeared before and if the difference between the current and previous indices is <= k.
The reference solution runs in O(n) time and O(min(n, k)) space.
The Contains Duplicate II solution and editorial walks through the full approach with reference code.
Problem statement
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Example 1:
Input: nums = [1,2,3,1], k = 3 Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1 Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2 Output: false
Constraints:
- 1 <= nums.length <= 105
- -109 <= nums[i] <= 109
- 0 <= k <= 105
Topics and companies
Topics: Array, Hash Table, Sliding Window.
Reported in interviews at Facebook, Amazon.
How to practise Contains Duplicate II on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(min(n, k)) space.
Open Contains Duplicate II in the code editor, or read the Contains Duplicate II editorial for a worked solution with its approach and complexity analysis.
Where Contains Duplicate II sits in the DSA pattern sheet
Problems related to Contains Duplicate II
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Continuous Subarrays — Medium, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Jump Game VII — Medium, same subpattern
- Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit — Medium, same subpattern
Contains Duplicate II FAQ
What is the LeetCode number of Contains Duplicate II?
Contains Duplicate II is LeetCode problem 219, rated Easy.
What pattern is used to solve Contains Duplicate II?
Contains Duplicate II is a Variable Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
What is the time complexity of Contains Duplicate II?
The reference solution runs in O(n) time and O(min(n, k)) space.
Which companies ask Contains Duplicate II?
Contains Duplicate II has been reported in interviews at Facebook, Amazon.