Posts

When numbers from $$\in$$ [0,n-1] are sorted in an array of size n. Their sorted position is equal to their index. Subset of numbers in array[i:j] can form a partition, if all elements in [i,j) are available in array[i:j]. For example [2,0,1] can form a partition, since they are at index 0, 1, 2 respectively. Sorted will involving swapping them at their correct position. The basic idea behind this solution is that we try to identify such partitions, where all elements required to be sorted in [i, j] are available in current partition. ...

For each word, we basically store all versions of it after removal of 1 character. For example, 1 2 3 4 5 6 hello -> ello -> removed h@0 hllo -> removed e@1 helo -> removed l@2 helo -> removed l@3 hell -> removed o@4 We can store: wordAfterRemoval,indexOfRemoval in hashmap. So whenever we search for a word like: hexlo then we can try removing it’s 2nd index and search: helo,2 in the map, which we will find. ...

Problem definition: For the output array, you need to calculate the absolute difference of each adjacent items. The number of unique absolute differences needs to be exactly k. For example in [1,3,2]: abs(1-3) = 2 abs(3-2) = 1 Thus [2,1] with 2 unique values as in example 2. credits: @Frans Valli Approach: Divide the array into 2 halves. The left half will contain numbers continously increasing by 1. The right half will contain numbers, such that the differences are continously decreasing by 1. ...

Suppose, while traversing the array you encounter a 132 pattern that violates the non-decreasing property. Now you have 2 options to fix this anomaly. a=1, b=3, c=2 Either we decrease b and make it equal to c i.e.b=c=2. Or we increase c to make it equal to b i.e. c=b=3. I would argue that we should always try to decrease b. Since, it enables us to have lower last value i.e. c. It decreases the chance of next number in the sequence violating the non-decreasing property. ...

We build a simple Tri where each node’s value is the sum of all words in the Tri that have same prefix as current node. Let me explain with a simple example. Suppose, we have an empty Tri. Insert "apple" with value=3. While inserting a key, we shall increase values of all intermediate nodes. Here’s how to Tri looks like after insertion: Now let’s insert "app" with value=2. Please note that we shall increase the value of intermediate nodes while inserting app. Therefore, the first 3 nodes will have value=5. ...