Contains Duplicate

Problem Overview

The Contains Duplicate problem from LeetCode asks you to determine if an array contains any duplicate elements.

Problem Statement: 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:

• Input: nums = [1,2,3,1]

• Output: true

• Input: nums = [1,2,3,4]

• Output: false

• Input: nums = [99,99]

• Output: true

Solution Approach

C# Solution - Sorting Approach

Sort the array first to group duplicate elements together, then iterate through the sorted array to check if any adjacent elements are equal. If two adjacent elements are the same, we've found a duplicate.

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        Array.Sort(nums);

        for(int i = 0; i < nums.Length - 1; i++) {
            if(nums[i] == nums[i+1]){
                return true;
            }
        }

        return false;
    }
}

Time Complexity: O(n log n) - due to sorting operation Space Complexity: O(1) - only constant extra space (sorting in-place)

Key Insights

1. Sorting First: Sort the array to group duplicate elements together, making them adjacent
2. Adjacent Comparison: After sorting, all duplicate pairs will be next to each other
3. Early Exit: Return true immediately when a duplicate is found, no need to check the entire array
4. Space Efficient: Sorting in-place uses only constant extra space, unlike HashSet which requires O(n) space
5. Trade-off: Uses more time (O(n log n)) but achieves optimal space complexity (O(1))
6. Array Bounds: Loop only up to nums.Length - 1 to avoid index out of bounds

Related Problems

• Valid Anagram
• Contains Duplicate II
• Contains Duplicate III

Video Tutorial

Watch the complete explanation and walkthrough in the video above for a detailed solution approach and implementation details.