I want to document my thought process on this Leetcode question, https://leetcode.com/problems/contains-duplicate.

First I'll try get an idea of what the function signature should be like while listening to the question. Then I'll start ask clarifying questions and come up with examples. After clarifying, I'll brainstorm some ideas to solve the problem. I want to try throwing different data structures at the problem for now, some may just be for the sake of considering them.

Function signature:

• boolean containsDuplicate(int[] nums)

Clarifying Questions:

• Input: null/empty/size than 2? sorted? range of values in nums?

• Output: How to handle invalid input?

Examples:

• nums = [1,3]

• nums = [1,1]

• nums = null, nums = [], nums = [1] // invalid

Brainstorm:

(n = nums.length)

1. Brute force: 2 for loops

   • For every num i, search through the list for duplicate.
     Can start searching at i+1.

   • time O(n^2)
     space O(1)

2. Sort first, then check if array is strictly increasing

   • time O(nlogn) ~ O(n^2) for java quicksort
     space O(logn) ~ O(n) for java quicksort

3. ArrayList<Integer> seen

   • Use ArrayList to hold a list of nums seen before.
     For every num, search through the seen list for duplicate.
     Must start searching at beginning of the list.

   • time O(n^2)
     space O(n)

4. Stack / Queue

   • Using Stack / Queue to hold list of nums seen before doesn't make sense, I still need to keep the items in the list, and not using pop() poll() makes this the same as using ArrayList.

5. boolean[] seen

   • Using boolean[] to keep track of whether a num has been seen only works if the values of nums is within a valid range.

   • time O(n)
     space O(length_of_range)

6. HashSet<Boolean> seen

   • Use HashSet to keep track of whether a num has been seen.

   • time O(n)
     space O(n)

7. Binary Search Tree

   • Use to hold a list of nums seen before.
     For every num, search through the tree for duplicate and insert if not duplicate.

   • time O(nlogn) // for search and insert
     space O(n)

Code:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length < 2) return false;

        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (!seen.add(num)) {
                return true;
            }
        }
        return false;
    }
}

Let me know if there is anything I should have considered, or has an error! I'm happy to get any feedback.