Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

Contains Duplicate

Array, Hash Table

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Solutions

The key insight to solve this problem is to realize that we need to keep track of the elements we have already encountered as we iterate through the array. If we encounter an element that we have seen before, we can immediately return true because we have found a duplicate. If we finish iterating through the array without finding any duplicates, we return false.

Approach – Brute Force Technique

The brute force approach involves checking each pair of elements in the array. If any pair is equal, return true. If no pairs are equal, return false.

Steps

  1. Iterate over the array: The outer loop (index i from 0 to nums.Length - 1) iterates over each element in the array.

  2. Check for duplicates: For each element nums[i], the inner loop (index j from i + 1 to nums.Length - 1) checks all the following elements in the array to see if they are equal to nums[i].

  3. Return true if a duplicate is found: If nums[i] is equal to nums[j], it means we have found a duplicate, so we immediately return true.

  4. Return false if no duplicates are found: If we finish iterating through the array without returning true, it means we have not found any duplicates, so we return false.

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        for (int i = 0; i < nums.Length; i++) {
            for (int j = i + 1; j < nums.Length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

Complexity

  • Time Complexity: O(n^2)

  • Auxiliary Space: O(1)

Approach – Sorting Technique

This approach involves sorting the array first, then checking each pair of adjacent elements. If any pair is equal, return true. If no pairs are equal, return false.

Steps

  1. Sort the array: The Array.Sort(nums) function sorts the array in ascending order. This operation has a time complexity of O(n log n), where n is the number of elements in the array.

  2. Iterate over the array: The loop for (int i = 0; i < nums.Length - 1; i++) iterates over each element in the array, except the last one. This is because we're comparing each element with its next neighbor, and the last element doesn't have a next neighbor.

  3. Check for duplicates: Inside the loop, the if (nums[i] == nums[i + 1]) statement checks if the current element is equal to the next element. Because the array is sorted, any duplicate elements will be adjacent to each other. So, if the current element is equal to the next element, it means we have found a duplicate, and we immediately return true.

  4. Return false if no duplicates are found: If we finish iterating through the array without returning true, it means we have not found any duplicates, so we return false.

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        Array.Sort(nums); //n log n
        for (int i = 0; i < nums.Length - 1; i++) //n times
         {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

Complexity

  • Time Complexity: O(n log n)

  • Auxiliary Space: O(1)

Approach – Hash Table Technique

We can use a data structure like a HashSet that allows for efficient insertions and lookups. We iterate through the array and insert each element into the HashSet. If an element is already in the HashSet, we return true. If we finish iterating through the array without finding any duplicates in the HashSet, we return false.

Steps

  1. Initialize: Create a new HashSet set. A HashSet is a collection of unique elements.

  2. Iterate over the array: The foreach loop iterates over each element num in the array nums.

  3. Check for duplicates: Inside the loop, the if (set.Contains(num)) statement checks if num is already in the HashSet set. If it is, it means we have found a duplicate, so we immediately return true.

  4. Add element to the set: If num is not in the set, we add it to the set using set.Add(num). This step is done for each element in the array.

  5. Return false if no duplicates are found: If we finish iterating through the array without returning true, it means we have not found any duplicates, so we return false.

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        HashSet<int> set = new HashSet<int>();
        foreach (int num in nums) {
            if (set.Contains(num)) {
                return true;
            }
            set.Add(num);
        }
        return false;
    }
}

Complexity

  • Time Complexity: O(n)

  • Auxiliary Space: O(n)

PreviousTwo Sum II - Input Array Is SortedNextMaximum Subarray

Last updated 1 year ago