- Input array should be sorted. Input array may or may not contain duplicate elements.
- Note that in the case of a sorted array, finding an element is going to take O(log n) time. But update operations like inserting an element or deleting an element are going to take O(n) time, because you would need to shift the remaining elements. If you want to perform both find and update in O(log n) time, then you are going to have to use a balanced binary search tree.
- Binary Search card on LC.
- Binary Search kicked you in the balls. Start going down the rabbit hole here. PDF from cs.cmu.edu. SO Question 1, SO Question 2, another blog post, this blog post has colors, blog post on Algorist.
- Read here on wikipedia for what happens with binary search in the case that the input array contains duplicate elements. Basically, the procedure may return any index whose element is equal to the target value, even if there are duplicate elements in the array. For example, if the array to be searched was [1,2,3,4,4,5,6,7] and the target was 4, then it would be correct for the algorithm to either return the 4th (index 3) or 5th (index 4) element. The regular procedure would return the 4th element (index 3) in this case. It does not always return the first duplicate (consider [1,2,4,4,4,5,6,7] which still returns the 4th element). However, it is sometimes necessary to find the leftmost element or the rightmost element for a target value that is duplicated in the array. In the above example, the 4th element is the leftmost element of the value 4, while the 5th element is the rightmost element of the value 4.

Binary Search using Template 1

: The key thing to understand in this template is that - Template #1 is used to search for an element or condition which can be determined by accessing a single index in the array. The search condition can be determined without having to look at the neighboring elements. No post-processing required because at each step, you are checking to see if the element has been found. If you reach the end, then you know the element is not found.
- Take note of the looping condition in the while loop and the changing of the left and the right variables in each loop iteration. Since we are using <= in the while loop, we have to change left and right accordingly. Contrast this with the way that we are doing the same thing in the case of Template #3 code below. -

Binary Search using Template 3

: This is used to search for an element or condition which requires accessing the current index and its immediate left and right neighbor's index in the array. Loop/Recursion ends when you have 2 elements left. Need to assess if the remaining elements meet the condition. Again, take note of the looping condition in the while loop. At the point of termination of the while loop, left + 1 == right. Also note that in this version of Binary Search, left and right are set to mid. Compare the same with the Template #1 being used above. - Comparison of the three templates is present here on LC.
- Explanation for why we are using l+(r-l)/2 instead of (l+r)/2.
- In binary search we find out the mid point and decide to either search on the left or right depending on some condition. Figure out the condition, and you should be good.
- Guess Number Higher or Lower to get you started.
- First Bad Version. Note how the solution of this problem is different from the above problem. You are kind of doing the same thing. In the above guessing number problem you are using Template#1, but in this problem you have to use Template#3.
- Find minimum in rotated sorted array
- Search in Rotated Sorted Array. Good practice problem. Both templates, Template#1 and Template#3 are used in the code.
- Find First and Last Position of Element in Sorted Array. Good problem to show how to handle duplicate elements in the case of binary search. If duplicate elements are present in the array, find the leftmost and the rightmost occurrences of the element.
- Find K Closest Elements. Good question. Hence you have decided not to do it?
- Closest Binary Search Tree Value. You are given a Binary Search Tree now, and you have to recursively iterate through the tree in order to find the element that you are looking for.
- Search in a Sorted Array of Unknown Size. How do you do a binary search in a sorted array whose size you do not know?
- Find Peak Element. Did not do this either.

- Card on LeetCode is present here.
- General Tips to keep in mind:
a) If iterating from the front of the array is not immediately giving an algo, try iterating from the end of the array instead.
b) If the algo is becoming too complicated when you are trying to do everything in one pass of the array, try splitting the tasks into multiple passes of the array. Use 2 or 3 for-loops to make multiple passes over the array and see if it simplifies the solution.
c) Two-Pointer technique can be very useful. Think of the two-pointer technique as a readIdx and a writeIdx. You generally increment the readIdx every loop because you would want to evaluate the next element of the array. If the current element being read satisfies certain conditions, then in that case you will copy the element and put it at the writeIdx, and increment both writeIdx and readIdx after that. At no point will the writeIdx ever become greater than the readIdx and hence we will never overwrite any elements that we have not read yet. Refer it here on LC.
d) General questions to consider: Can it contain duplicate values? Can it contain negative values?
e) Do sanity check at the start of Array problems. Check that the array is not null and the length > 0.
f) If at anytime you feel like there is an O(n^2) algo only that can solve the problem, then sort the input and do a binary search. That would still be faster.
- Java always initializes empty Array slots to null if the Array contains objects, or to default values if it contains primitive types. For example, the array int[] would contain the default value of 0 for each element, float[] would contain default values of 0.0, and boolean[] would contain default values of false.
- Max Consecutive Ones. Note when you are counting the maximum value of max ones in an array, you might have been given an array like this: [0,1,1,1,1]. In this case, you would end up never updating the overallMaxNumOfOnes variable. Hence, do not forget to return the Max of the two numbers. - Find Numbers with Even Number of Digits. Note how we can count the number of digits in a number using log to the base 10 in Approach 2. Also note how we are counting the number of digits by extracting each digit in approach 1.

- Difference between equals and deepEquals on SO.
- Difference between equals and Arrays.equals on SO. Note that array1.equals(array2) is the same as array1 == array2, i.e. is it the same array. Arrays.equals(array1, array2) compares the contents of the arrays. Note that Arrays.equals() does not work as expected for multidimensional arrays, it only compares items of the 1st dimension for reference equality. That's why we have Arrays.deepEquals(Object[], Object[]). Arrays.deepEquals(Object[], Object[]) is a recursive call. Two arrays are equal if they contain the same elements in the same order. Two arrays are also equal if both of them are null.
- Remember that Objects.equals(arg1, arg2) internally simply calls arg1.equals(arg2) method of arg1 (the first argument passed into the Objects.equals method). Keep that in mind when you see the behavior of equals and Objects.equals in the case of arrays.
- Sorting an array, without having to convert it into a List, is a story of its own. Read here on Baeldung.

- Refer how to use a Comparator here. Also keep in mind everything we went over regarding removing/modifying elements in a list while iterating over the same list like we discussed over here.
- How to check if two lists have the same elements on SO.
- Calculating the intersection and union of array lists on SO. Traditionally, unions and intersections defined only for sets, not lists. So it's not exactly clear what you mean by union of two lists for example. For instance, what happens if there are duplicate elements in one of the list? Are both of the elements included in the union. What if duplicate elements in intersection. All of these are things that you will have to think about before you try performing set operations on lists.
- Note that a List does not allow inserting an element at any arbitrary index by using the add(int index, E element) method. If the List is empty, you can use only 0 as the index to add the first element to the list. If you have five elements in a List, you must use indexes between 0 and 5 to add a new element to the List. The index from 0 to 4 will insert an element between existing elements. The index of 5 will append the element to the end of the List. This implies that a List must grow sequentially. You cannot have a sparse List such as a List with first element and tenth element, leaving second to ninth elements non-populated. This is the reason that a List is also known as a sequence.
- The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation. Source Oracle Java Docs.
- There is a subList method present in the List interface as well. Write about that.

- You can sort arrays using Arrays.sort(arrayName). You can also pass in a custom Comparator as a second args to sort it by something other than the natural order. Refer here. - Find Pivot Index
- Plus One

- Vanilla traversal over a 2D array: - Diagonal Travers. Good insight into the indices in this solution in the comments here.
- TODO: Spiral Matrix
- Pascal's Triangle

- Add Binary. Basic template for questions involving adding two numbers when input is as strings. - Implement strStr()
- Longest Common Prefix

- Two pointer technique is often used on a sorted array.
- Reverse String. Two things to note here: - Array Partition I. Another application of Counting Sort. This one has -ve numbers as well.
- Two Sum II - Input array is sorted. If the input array is sorted and you are trying to find if two elements of the array add up to a target sum, then you can use the 2 pointer technique as well. Keep the left and the right indices at the two ends of the array. Find their sum. If the curr sum is greater than the target, then you need to consider a smaller element, in which case you will move the right pointer to the left. On the other hand, if the curr sum is lesser than the target sum, it means that you need to consider a larger number next, in which case you should move the left pointer to the right.
- Minimum Size Subarray Sum. Excellent question to understand the basics of a sliding window pattern. Note carefully how the window is being used. Also refer the wrong method that you were using in order to create the window. The question page and the related discussion page has some similar questions that use the same technique. Refer the post here on LC for a template. TODO.

- The two-pointer technique sometimes will relate to Greedy Algorithm which helps us design our pointers' movement strategy.
- Rotate Array. You are still using extra space. Go over the other two approaches that are present in the solution.
- Reverse Words in a String. You can either use the built-in methods or not. Another similar problem is Reverse Words in a String III.

- There are two different kinds of hash datastructures: hash set and hash map. The HashSet is one implementation of the Set datastructure that does not allow duplicated values. The HashMap is an implementation of the Map datastructure that stores elements in the form of <key, value>.
- Design HashSet. Good solution with write-up about the different ways that collision can be handled. Separate Chaining, Open Addressing, and 2 choice hashing.
- Design HashMap. Note that in the case when there are two or more elements that have the same hash value, both the elements will be mapped to the same bucket. Suppose the elements mapped to the same bucket are stored in a list. In this case, if you want to delete one of the elements (and suppose you have a reference to the element that you want to delete), once you have deleted the element, you will have to move all of the elements, to the right of the deleted element, one space to the left. You can get around this by first swapping the element that you want to delete with the last element of the list and then deleting the last element instead. Now no need of shifting any elements once the required element has been deleted.
- You have not done the above two problems but just copied the solution in order to see the hidden stuff.
- Good answer on SO explaining how Hash Map works.
- Note that if you are using Strings as keys for your Set/Map, then the complexity of checking whether a String exists in the set/map or not is going to be O(m), where m is the number of characters in the string. Explained on SO here. Once you add a String object to a Set/Map, the hashCode of the string is stored/cached in that String object. Hence, later on if you use the same instance of the string to check for something like contains, the Set/Map will not have to recalculate the hash again, since it will just use the cached value instead giving you O(1) time complexity. But if you use a new string object that is logically equal to the earlier string that you added, but is a completely new instance of String, the hash value of it will have to be calculated all over again giving you O(m) once again.
- Note that when it comes to Set/Map implementations, we have the TreeSet and TreeMap implementations as well. The time complexity of basic operations (add, remove, contains) is O(logN) on a TreeSet. The TreeMap provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Also read the Computational Complexity of TreeSet methods in Java on SO.
- Point to note is that while the HashSet provides O(1) time complexity for basic operations like add, remove, contains, size, the TreeSet/TreeMap do the add, remove, contains in O(logN). Also note that the HashMap has a containsKey and containsValue method. The containsKey has a O(1) time, whereas the containsValue has O(n) time because containsKey() is just a get() that throws away the retrieved value.
- Baeldung: Java Collections Complexity. For HashSet, LinkedHashSet, and EnumSet, the add(), remove() and contains() operations cost constant O(1) time thanks to the internal HashMap implementation. Likewise, the TreeSet has O(log(n)) time complexity for the operations listed in the previous group. This is because of the TreeMap implementation.
- Baeldung: Java HashMap Basics
- Baeldung: Java HashMap Advanced

- Basic operations in a HashSet
- Also recall the discussion we had about modifying a hashset while iterating over the same HashSet. It is going to throw a ConcurrentModificationException. Like we discussed here.
- Tree Set behavior explained here on SO.
- Contains Duplicate. 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. Note that you can use the return value of the add() method to check if the element being added to the set already existed in the Set or not. Point being, you do not need to separately use contains to check. - Single Number. Given a non-empty array of integers nums, every element appears twice except for one. Find that element that occurs only once. - Happy Number.

- Each element in a Map represents a key-value pair as <key, value>. A <key, value> pair is also known as an entry in the map. The key and the value must be reference types. You cannot use primitive types (int, double, etc.) for either keys or values in a map.
- Map does not allow any duplicate keys. Each key is mapped to exactly one value. In other words, each key in a Map has exactly one value. Values do not have to be unique. That is, two keys may map to the same value.
- The view operations category contains three methods. Each returns a different view of a Map. You can view all keys in a Map as a Set, all values as a Collection, and all <key, value> pairs as a Set. Note that all keys and all <key, value> pairs are always unique in a Map and that is the reason why you get their Set views. Since a Map may contain duplicate values, you get a Collection view of its values.
- Make sure to read the different ways that we can remove elements from a Map while iterating over the same Map using the removeIf method here on this page.
- If you want to initialize a HashMap from multiple items, you can use the Map.of() method as mentioned in this SO answer. Note that this creates an ImmutableMap, and also you can only add a max of 10 entries to the map using this method.
- Basic Operations involving a Hash Map. - Isomorphic Strings. Note the below solution. It uses the technique of associating each key with a Collection, like a List. Basically we are trying to store all the positions that a character appears in a String. Can be used as a general template for these kinds of questions. - First Unique Character in a String. This is what I wanted to explain to you. Instead of using a datastructure like a LinkedHashMap to store the order of iteration over the string (and then iterating over the map to get the required answer), use the given string to iterate and get the values from the HashSet to see if the condition is satisfied.

- TODO.

- Sometimes we only need to access the largest or the smallest element in a dataset. We do not care about the order of the other data in the dataset. To efficiently access, we make use of the heap data structure.

- Sometimes we only need to access the largest or the smallest element in a dataset. We do not care about the order of the other data in the dataset. To efficiently access, we make use of the heap data structure.

- // TODO

1) Create an array using int[] numbers = new int[size];. Or you do: int[] numbers = new int[]{1,2,3,4,5};
2) The problem with doing an if-else ladder in a while block is that if there is no else condition, you are probably going to run into an infinite loop condition where none of the else if clauses are true, and hence the loop end condition never gets changed. So this is a bad idea. You need a else block to catch everything else.