The Contains Duplicate problem is a common algorithmic challenge that asks you to determine whether an array contains any duplicate elements. This problem frequently appears in coding interviews and is an excellent opportunity to showcase your ability to manipulate arrays and optimize solutions for efficiency.

In this post, we will explore different approaches to solve the Contains Duplicate problem in Kotlin. We’ll discuss the naive solution using brute force, more efficient approaches using sorting and sets, and we’ll dive into time and space complexity analysis. We'll also handle edge cases to ensure the robustness of the solution.

Problem Definition

You are given an integer array nums. Your task is to determine if any value appears at least twice in the array. The function should return true if any value appears more than once, and false if every element is distinct.

Example:

Input: nums = intArrayOf(1, 2, 3, 1)
Output: true

Input: nums = intArrayOf(1, 2, 3, 4)
Output: false

Input: nums = intArrayOf(1, 1, 1, 3, 3, 4, 3, 2, 4, 2)
Output: true

Constraints:

  • The array can contain up to (10^5) elements.
  • The values in the array can range from (-10^9) to (10^9).

Approach 1: Brute-Force Solution

Explanation:

The brute-force approach checks every pair of elements in the array to see if any two elements are the same. This can be achieved using two nested loops, where the outer loop selects one element, and the inner loop checks for any duplicates.

Code Implementation:

fun containsDuplicate(nums: IntArray): Boolean {
    for (i in nums.indices) {
        for (j in i + 1 until nums.size) {
            if (nums[i] == nums[j]) {
                return true  // Duplicate found
            }
        }
    }
    return false  // No duplicates found
}

// Test cases
fun main() {
    println(containsDuplicate(intArrayOf(1, 2, 3, 1)))  // Output: true
    println(containsDuplicate(intArrayOf(1, 2, 3, 4)))  // Output: false
}

Time and Space Complexity:

  • Time Complexity: O(n²), where n is the number of elements in the array. This is due to the two nested loops.
  • Space Complexity: O(1), since no additional space is used aside from a few variables.

Explanation:

The brute-force solution is simple but inefficient for large arrays. It compares every element with every other element, making it impractical for large inputs due to the O(n²) time complexity.

Approach 2: Sorting-Based Solution

Explanation:

A more efficient way to solve this problem is by sorting the array first. Once the array is sorted, any duplicates will be adjacent to each other. We can then iterate through the array and check if any two consecutive elements are the same.

Code Implementation:

fun containsDuplicate(nums: IntArray): Boolean {
    nums.sort()  // Sort the array
    for (i in 1 until nums.size) {
        if (nums[i] == nums[i - 1]) {  // Compare adjacent elements
            return true  // Duplicate found
        }
    }
    return false  // No duplicates found
}

// Test cases
fun main() {
    println(containsDuplicate(intArrayOf(1, 2, 3, 1)))  // Output: true
    println(containsDuplicate(intArrayOf(1, 2, 3, 4)))  // Output: false
}

Time and Space Complexity:

  • Time Complexity: O(n log n), where n is the number of elements. This is due to the sorting operation, which dominates the time complexity.
  • Space Complexity: O(1) if sorting is done in place using nums.sort().

Explanation:

Sorting the array ensures that any duplicates will be placed next to each other. We then iterate through the sorted array, comparing each element with its neighbor. If any two consecutive elements are the same, the function returns true. This approach is more efficient than brute force, but sorting can still be slow for large inputs.

Approach 3: HashSet-Based Solution (Optimal)

Explanation:

The most efficient way to solve this problem is by using a HashSet in Kotlin. A HashSet only stores unique values and provides O(1) time complexity for insertions and lookups. As we iterate through the array, we can check if an element already exists in the set. If it does, we return true, indicating a duplicate exists. If not, we add the element to the set and continue.

Code Implementation:

fun containsDuplicate(nums: IntArray): Boolean {
    val seen = mutableSetOf<Int>()  // Create a HashSet to store unique elements
    for (num in nums) {
        if (num in seen) {  // If the element is already in the set
            return true  // Duplicate found
        }
        seen.add(num)  // Add the element to the set
    }
    return false  // No duplicates found
}

// Test cases
fun main() {
    println(containsDuplicate(intArrayOf(1, 2, 3, 1)))  // Output: true
    println(containsDuplicate(intArrayOf(1, 2, 3, 4)))  // Output: false
}

Time and Space Complexity:

  • Time Complexity: O(n), where n is the number of elements in the array. We iterate through the array once, and each insertion or lookup in the HashSet takes O(1) time on average.
  • Space Complexity: O(n), since we use extra space to store the elements in the set.

Explanation:

Using a HashSet ensures that we only need to loop through the array once, while maintaining a collection of unique elements. This solution is optimal in terms of time complexity (O(n)) and works well even for large inputs.

Edge Cases

When solving the Contains Duplicate problem, it is important to consider the following edge cases:

  1. Empty Array:
    If the array is empty, there are no elements to check for duplicates, so the function should return false.

    println(containsDuplicate(intArrayOf()))  // Output: false

  2. Array with One Element:
    If the array contains only one element, it is impossible for there to be any duplicates, so the function should return false.

    println(containsDuplicate(intArrayOf(1)))  // Output: false

  3. Array with All Unique Elements:
    If the array contains all unique elements, the function should return false.

    println(containsDuplicate(intArrayOf(1, 2, 3, 4, 5)))  // Output: false

  4. Array with All Duplicates:
    If the entire array consists of the same element repeated multiple times, the function should return true.

    println(containsDuplicate(intArrayOf(1, 1, 1, 1, 1)))  // Output: true

  5. Negative Numbers:
    Ensure the solution correctly handles negative numbers as well as positive numbers.

    println(containsDuplicate(intArrayOf(-1, -2, -3, -1)))  // Output: true

  6. Large Inputs:
    The function should efficiently handle arrays with a large number of elements (e.g., (10^5) elements).

    val nums = IntArray(100000) { it }
nums[99999] = 0  // Introduce a duplicate at the end
println(containsDuplicate(nums))  // Output: true

Conclusion

In this post, we explored multiple approaches to solving the Contains Duplicate problem in Kotlin. The brute-force solution is easy to implement but inefficient for large arrays, while the sorting-based solution offers a more efficient approach but still requires O(n log n) time. The optimal solution uses a HashSet to achieve O(n) time complexity, making it the best choice for handling large datasets. By addressing various edge cases, we ensure that the solution is robust and can handle all inputs.