LeetCode Curated List of 75 Problems.

Algorithms

Math
Array
Bit Manipulation
Dynamic Programming
Graph
Interval
Linked List
Matrix
String
Tree
Heap/Priority Queue
Binary Search
Recursion
Sliding Window
Greedy and Backtracking

Math

#	Title	url	Time	Space	Difficulty	Tag	Note
0012	Integer to Roman	https://leetcode.com/problems/integer-to-roman/	O(n)	O(1)	Medium
0013	Roman to Integer	https://leetcode.com/problems/roman-to-integer/	O(n)	O(1)	Easy
0149	Max Points on a Line	https://leetcode.com/problems/max-points-on-a-line/	O(n^2)	O(n)	Hard		Linear Equation `ax + by + c = 0`
0204	Count Primes	https://leetcode.com/problems/count-primes/	O( NLog(Log(N)) )*	O(N)	Easy		Sieve of Eratosthenes
0372	Super Pow	https://leetcode.com/problems/super-pow/	O(n)	O(1)	Medium
0509	Fibonacci Number	https://leetcode.com/problems/fibonacci-number/	O(logn)	O(1)	Easy	variant of Climbing Stairs	Matrix Exponentiation, Binet's Formula
1390	Four Divisors	https://leetcode.com/problems/four-divisors/	O(N+KLog(Log(K)))*, where, N = max(nums), M=len(nums), K is len(primes)	O(N+M+K^2), where, N = max(nums), M=len(nums), K is len(primes)	Medium		Sieve of Eratosthenes
1390	Four Divisors	https://leetcode.com/problems/four-divisors/	O(N sqrt(M))*, where, N = length of nums and M = nums[i]	O(1)	Medium		Recursion

Array

#	Title	url	Time	Space	Difficulty	Tag	Note
0001	Two Sum	https://leetcode.com/problems/two-sum/	O(n)	O(n)	Easy
0121	Best Time to Buy and Sell Stock	https://leetcode.com/problems/best-time-to-buy-and-sell-stock/	O(n)	O(1)	Easy
0217	Contains Duplicate	https://leetcode.com/problems/contains-duplicate/	O(n)	O(n)	Easy
0238	Product of Array Except Self	https://leetcode.com/problems/product-of-array-except-self/	O(n)	O(1)	Medium	LintCode
0053	Maximum Subarray	https://leetcode.com/problems/maximum-subarray/	O(n)	O(1)	Medium		`Kadane's Algorithm`
0152	Maximum Product Subarray	https://leetcode.com/problems/maximum-product-subarray/	O(n)	O(1)	Medium
0153	Find Minimum in Rotated Sorted Array Solution 1	https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/	O(logn)	O(1)	Medium
0033	Search in Rotated Sorted Array Solution 1	https://leetcode.com/problems/search-in-rotated-sorted-array/	O(logn)	O(1)	Medium	CTCI
0015	3 Sum	https://leetcode.com/problems/3sum/)	O(n^2)	O(1)	Medium		Two Pointers
0011	Container With Most Water	https://leetcode.com/problems/container-with-most-water/	O(n)	O(1)	Medium

LC-121:Best Time to Buy and Sell Stock

Solution Explanation

Approach: Dynamic Programming + State Machine
=================================================================================================================================================================

- It is impossible to have stock to sell on first day, so -infinity is set as initial value for cur_hold and cur_not_hold is set to 0
- Iterate through the list of prices
  + Either keep in hold, or just buy today with stock price
  + Either keep in not holding, or just sell today with stock price
- Max profit must be in not-hold state

                                  Sell
                                  + stock price to balance
                      +------------------------------------------------+
                     /                                                  \
   ___    _________|/_                                                   \_________    ___
  /  _\| /         \                                                     /         \ |/_  \
 |      + Not Hold  +                                                   +    Hold   +      | Keep in hold
  \___/  \_________/                                                     \_________/  \___/
                    \                                                    /
 Keep in not holding \                                                  /
                      +------------------------------------------------+
                                  Buy
                                  - stock price from balance

Complexity Analysis:

Time  : O(N)
========================
We traverse the list containing n elements only once.

Space : O(1)
========================
No need for a dp array. We have replaced dp array with a variable called cur_not_hold.

from typing import List

def maxProfit(prices: List[int]) -> int:
    if not price: return 0

    # It is impossible to have stock to sell on first day, so -infinity is set as initial value
    cur_hold, cur_not_hold = -float('inf'), 0
            
    for stock_price in prices:        
        prev_hold, prev_not_hold = cur_hold, cur_not_hold
            
        # either keep in hold, or just buy today with stock price
        cur_hold = max(prev_hold, -stock_price)
            
        # either keep in not holding, or just sell today with stock price
        cur_not_hold = max(prev_not_hold, prev_hold + stock_price)
        
    # max profit must be in not-hold state
    return cur_not_hold if prices else 0

if __name__ == "__main__":
    #Input: prices = [7,1,5,3,6,4]
    #Output: 5
    #Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
    prices = [7,1,5,3,6,4]
    print(maxProfit(prices))

fun maxProfit(prices: IntArray): Int {
    //if (prices?.isEmpty() ?: true) return 0
    if (prices.isEmpty()) return 0
    // It is impossible to have stock to sell on first day, so -infinity is set as initial value
    var curHold = Int.MIN_VALUE
    var curNotHold = 0

    for (stockPrice in prices) {
        val prevHold = curHold
        val prevNotHold = curNotHold
            
        // either keep in hold, or just buy today with stock price
        curHold = maxOf(prevHold, stockPrice.unaryMinus())
            
        // either keep in not holding, or just sell today with stock price
        curNotHold = maxOf(prevNotHold, prevHold + stockPrice)
    }
    // max profit must be in not-hold state
    return curNotHold
}

fun main(args: Array<String>) {
    //Input: prices = [7,1,5,3,6,4]
    //Output: 5
    //Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
    var prices = intArrayOf(7, 1, 5, 3, 6, 4)
    println(maxProfit(prices))
    //Input: prices = [7,6,4,3,1]
    //Output: 0
    //Explanation: In this case, no transactions are done and the max profit = 0.
    prices = intArrayOf(7, 6, 4, 3, 1)
    println(maxProfit(prices))
    //Input: prices = []
    //Output: 0
    prices = intArrayOf()
    println(maxProfit(prices))
}

⬆️ Back to Top

LC-238:Product of Array Except Self

Solution Explanation

=================================================================================================================================================================
Approach 1: Left and Right Arrays that capture the multiplication product scanning from left-to-right or right-to-left.
=================================================================================================================================================================
- We maintain a left and right array that captures the multiplication product scanning from left-to-right or right-to-left.
- The time complexity is two linear traversals, thus it's linear time.

- The tricky part is to keep a multiplicative counter with result till its previous element (not its self),
  and assign this value on to its left/right_array.

=================================================================================================================================================================
Approach 2: Optimized Space Solution. Without using extra memory of left and right product list.
=================================================================================================================================================================
Step 1. Create a list that contains the product of all left side elements except the current index of nums element.
Step 2. Create a variable of the right product and multiply with what we have in Step 1 (List that contains all the
        left side produts except the current index itself) through the loop --> this will calculate the product of
        array except for self.
Step 3. Keep updating the right product and loop.
Step 4. Return the answer.

Complexity Analysis:

=================================================================================================================================================================
Approach 1: Left and Right Arrays that capture the multiplication product scanning from left-to-right or right-to-left.
=================================================================================================================================================================
Time complexity : O(N) [ Technically O(2N) ]
========================
We traverse the list containing N elements twice. Each look up in the list costs only O(1) time.

Space complexity : O(1) [ As per problem, the output array does not count as extra space for space complexity analysis. ]
========================
Constant space since we only create a single output array to store the results.

=================================================================================================================================================================
Approach 2: Optimized Space Solution. Without using extra memory of left and right product list.
=================================================================================================================================================================
Time complexity : O(N) [ Technically O(2N) ]
========================
We traverse the list containing N elements twice. Each look up in the list costs only O(1) time.

Space complexity : O(1) [ As per problem, the output array does not count as extra space for space complexity analysis. ]
========================
Constant space since we only create a single output array to store the results.

from typing import List
import unittest

class Solution(object):
    #
    # -------------------------------------------------------------------------------------------------------------------------
    # Approach 1: Left and Right Arrays that capture the multiplication product scanning from left-to-right or right-to-left.
    # -------------------------------------------------------------------------------------------------------------------------
    #
    # TC: O(N)
    # SC: O(N)
    def productExceptSelf_Solution_1(self, nums: List[int]) -> List[int]:
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums: return []
        
        l = len(nums)
        left_arr, right_arr, left, right = [1]*l, [1]*l, 1, 1
        
        for i in range(1, l):
            left *= nums[i-1]
            left_arr[i] = left
        
        for j in range(l-2, -1, -1):
            right *= nums[j+1]
            right_arr[j] = right
        
        return [tup[0]*tup[1] for tup in zip(left_arr, right_arr)]

    #
    # -------------------------------------------------------------------------------------------------------------------------
    # Approach 2: Optimized Space Solution. Without using extra memory of left and right product list.
    # -------------------------------------------------------------------------------------------------------------------------
    # TC: O(N)
    # SC: O(1) [ excluding the output/result array, which does not count towards extra space, as per problem description. ]
    def productExceptSelf_Solution_2(self, nums: List[int]) -> List[int]:
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        length_of_list = len(nums)
		result = [0]*length_of_list
		
        # update result with left product.
        result[0] = 1
        for i in range(1, length_of_list):
            result[i] = result[i-1] * nums[i-1]

        right_product = 1
        for i in reversed(range(length_of_list)):
            result[i] = result[i] * right_product
			right_product *= nums[i]

        return result

class Test(unittest.TestCase):
    def setUp(self) -> None:
        pass

    def tearDown(self) -> None:
        pass

    def test_reverseList(self) -> None:
        sol = Solution()
        for nums, solution in (
            [
                [1,2,3,4],
                [24,12,8,6],
            ],
            [
                [-1,1,0,-3,3],
                [0,0,9,0,0]
            ]
        ):
            self.assertEqual(
                sol.productExceptSelf_Solution_1(nums),
                solution
            )
            self.assertEqual(
                sol.productExceptSelf_Solution_2(nums),
                solution
            )

if __name__ == "__main__":
    ##Input: nums = [1,2,3,4]
    ##Output: [24,12,8,6]
    #nums = [1,2,3,4]
    #print(productExceptSelf(nums))
    ##Input: nums = [-1,1,0,-3,3]
    ##Output: [0,0,9,0,0]
    #nums = [-1,1,0,-3,3]
    #print(productExceptSelf(nums))
	unittest.main()

fun productExceptSelf(nums: IntArray): IntArray {
    // create a list for output
    val results = IntArray(nums.size)
    // edge case
    if (nums.isEmpty()) return results

    // Step_#1
    // record product of terms on the left hand side        
    results[0] = 1
    for (i in 1 until nums.size) {
        results[i] = results[i - 1] * nums[i - 1]
    }

    // Step_#2
    // Update array elements as the product of ( product of left hand side ) * ( produt of right hand side )
    var right = 1
    for (i in nums.size - 1 downTo 0) {
        results[i] *= right
        right *= nums[i]
    }
    return results
}

fun main(args: Array<String>) {
    //Input: nums = [1,2,3,4]
    //Output: [24,12,8,6]
    var nums = intArrayOf(1,2,3,4)
    //contentToString() deprecated from kotlin version 1.4 onwards
    //println(productExceptSelf(nums).contentToString())
    println(productExceptSelf(nums).joinToString(","))

    //Input: nums = [-1,1,0,-3,3]
    //Output: [0,0,9,0,0]
    nums = intArrayOf(-1,1,0,-3,3)
    //contentToString() deprecated from kotlin version 1.4 onwards
    //println(productExceptSelf(nums).contentToString())
    println(productExceptSelf(nums).joinToString(","))
}

⬆️ Back to Top

LC-152:Maximum Product Subarray

Solution Explanation

Kadane's Algorithm
=================================================================================================================================================================
In this solution we keep track of both the minimum and the maximum subarray encountered so far. 
This is done in a Kadane like fashion, where the updates for both the current minimal streak and maximal streak depend on the other, 
while the maximum encountered so far only depends on the current maximum, and the updated current maximal streak.

Complexity Analysis:

Time  : O(N)
========================
The time complexity of Kadane’s algorithm is O(N) because there is only one for loop which scans the entire array exactly once.

Space : O(1)
========================
Kadane’s algorithm uses a constant space. So, the space complexity is O(1).

from typing import List

def maxProduct(nums: List[int]) -> int:
    ## RC ##
    ## APPROACH : KADANES ALGORITHM ##

    ## TIME COMPLEXITY : O(N) ##
    ## SPACE COMPLEXITY : O(1) ##

    # 1. Edge Case : Negative * Negative = Positive
    # 2. So we need to keep track of minimum values also, as they can yield maximum values.
    global_max = prev_max = prev_min = nums[0]
    for i in range(1, len(nums)):
        curr_min = min(prev_max*nums[i], prev_min*nums[i], nums[i])
        curr_max = max(prev_max*nums[i], prev_min*nums[i], nums[i])
        global_max = max(global_max, curr_max)
        prev_max = curr_max
        prev_min = curr_min
    return global_max

if __name__ == "__main__":
    #Input: nums = [2,3,-2,4]
    #Output: 6
    #Explanation: [2,3] has the largest product 6.    nums = [-2,1,-3,4,-1,2,1,-5,4]
    nums = [2,3,-2,4]
    print(maxProduct(nums))

fun maxProduct(nums: IntArray): Int {
    var maxGlobal = nums[0]
    var prevMax = nums[0]
    var prevMin = nums[0]
    for (i in 1 until nums.size) {
        val currMin = minOf(prevMax*nums[i], prevMin*nums[i], nums[i])
        val currMax = maxOf(prevMax*nums[i], prevMin*nums[i], nums[i])

        maxGlobal = maxOf(maxGlobal, currMax)
        prevMax = currMax
        prevMin = currMin
    }

    return maxGlobal
}

fun main(args: Array<String>) {
    //Input: nums = [2,3,-2,4]
    //Output: 6
    //Explanation: [2,3] has the largest product 6.    nums = [-2,1,-3,4,-1,2,1,-5,4]
    val nums = intArrayOf(2,3,-2,4)
    println(maxProduct(nums))
}

⬆️ Back to Top

LC-153:Find Minimum in Rotated Sorted Array Solution 1

Solution Explanation:

Binary Search Algorithm
=================================================================================================================================================================

Algorithm

1. Find the mid element of the array.

2. If mid element > first element of array this means that we need to look for the inflection point on the right of mid.

3. If mid element < first element of array this that we need to look for the inflection point on the left of mid.

          6 > 4
     +-------------+
     |             |
    \|/            |
 +---*--+------+---*--+------+------+------+
 |   4  |   5  |   6  |   7  |   2  |   3  |
 +------+------+------+------+------+------+
   Left           Mid                 Right
                     ---------------------->

In the above example mid element 6 is greater than first element 4. Hence we continue our search for the inflection point to the right of mid.

4 . We stop our search when we find the inflection point, when either of the two conditions is satisfied:

nums[mid] > nums[mid + 1] Hence, mid+1 is the smallest.

nums[mid - 1] > nums[mid] Hence, mid is the smallest.

                          +------+
                          |      |
                         \|/     |
 +------+------+------+---*--+---*--+------+
 |   4  |   5  |   6  |   7  |   2  |   3  |
 +------+------+------+------+------+------+
                        Left    Mid   Right

In the above example. With the marked left and right pointers. 
The mid element is 2. The element just before 2 is 7 and 7>2 i.e. nums[mid - 1] > nums[mid]. 
Thus we have found the point of inflection and 2 is the smallest element.

Detailed Algorithm
-----------------------

1) set left and right bounds
2) left and right both converge to the minimum index; DO NOT use left <= right because that would loop forever
  2.1) find the middle value between the left and right bounds (their average);
       can equivalently do: mid = left + (right - left) // 2,
       if we are concerned left + right would cause overflow (which would occur
       if we are searching a massive array using a language like Java or C that has
       fixed size integer types)
  2.2) the main idea for our checks is to converge the left and right bounds on the start
       of the pivot, and never disqualify the index for a possible minimum value.
  2.3) in normal binary search, we have a target to match exactly,
       and would have a specific branch for if nums[mid] == target.
       we do not have a specific target here, so we just have simple if/else.
  2.4) if nums[mid] > nums[right]
    2.4.1) we KNOW the pivot must be to the right of the middle:
           if nums[mid] > nums[right], we KNOW that the
           pivot/minimum value must have occurred somewhere to the right
           of mid, which is why the values wrapped around and became smaller.
    2.4.2) example:  [3,4,5,6,7,8,9,1,2]
           in the first iteration, when we start with mid index = 4, right index = 9.
           if nums[mid] > nums[right], we know that at some point to the right of mid,
           the pivot must have occurred, which is why the values wrapped around
           so that nums[right] is less then nums[mid]
    2.4.3) we know that the number at mid is greater than at least
           one number to the right, so we can use mid + 1 and
           never consider mid again; we know there is at least
           one value smaller than it on the right
  2.5) if nums[mid] <= nums[right]
    2.5.1) here, nums[mid] <= nums[right]:
           we KNOW the pivot must be at mid or to the left of mid:
           if nums[mid] <= nums[right], we KNOW that the pivot was not encountered
           to the right of middle, because that means the values would wrap around
           and become smaller (which is caught in the above if statement).
           this leaves the possible pivot point to be at index <= mid.

    2.5.2) example: [8,9,1,2,3,4,5,6,7]
           in the first iteration, when we start with mid index = 4, right index = 9.
           if nums[mid] <= nums[right], we know the numbers continued increasing to
           the right of mid, so they never reached the pivot and wrapped around.
           therefore, we know the pivot must be at index <= mid.

    2.5.3) we know that nums[mid] <= nums[right].
           therefore, we know it is possible for the mid index to store a smaller
           value than at least one other index in the list (at right), so we do
           not discard it by doing right = mid - 1. it still might have the minimum value.

3) at this point, left and right converge to a single index (for minimum value) since
   our if/else forces the bounds of left/right to shrink each iteration:

4) when left bound increases, it does not disqualify a value
   that could be smaller than something else (we know nums[mid] > nums[right],
   so nums[right] wins and we ignore mid and everything to the left of mid).

5) when right bound decreases, it also does not disqualify a
   value that could be smaller than something else (we know nums[mid] <= nums[right],
   so nums[mid] wins and we keep it for now).

6) so we shrink the left/right bounds to one value,
   without ever disqualifying a possible minimum.

Complexity Analysis:

Time  : O(log(N))
========================
Same as Binary Search O(log(N))

Space : O(1)
========================

from typing import List

def findMin(nums: List[int]) -> int:
    """
    :type nums: List[int]
    :rtype: int
    """
    # set left and right bounds
    left, right = 0, len(nums)-1

    # left and right both converge to the minimum index;
    # DO NOT use left <= right because that would loop forever
    while left < right:
        # find the middle value between the left and right bounds (their average);
        # can equivalently do: mid = left + (right - left) // 2,
        # if we are concerned left + right would cause overflow (which would occur
        # if we are searching a massive array using a language like Java or C that has
        # fixed size integer types)
        #mid = (left + right) // 2
        mid = left + (right - left) // 2
            
        # the main idea for our checks is to converge the left and right bounds on the left
        # of the pivot, and never disqualify the index for a possible minimum value.

        # in normal binary search, we have a target to match exactly,
        # and would have a specific branch for if nums[mid] == target.
        # we do not have a specific target here, so we just have simple if/else.
            
        if nums[mid] > nums[right]:
            # we KNOW the pivot must be to the right of the middle:
            # if nums[mid] > nums[right], we KNOW that the
            # pivot/minimum value must have occurred somewhere to the right
            # of mid, which is why the values wrapped around and became smaller.

            # example:  [3,4,5,6,7,8,9,1,2] 
            # in the first iteration, when we left with mid index = 4, right index = 9.
            # if nums[mid] > nums[right], we know that at some point to the right of mid,
            # the pivot must have occurred, which is why the values wrapped around
            # so that nums[right] is less then nums[mid]

            # we know that the number at mid is greater than at least
            # one number to the right, so we can use mid + 1 and
            # never consider mid again; we know there is at least
            # one value smaller than it on the right
            left = mid + 1
        else:
            # here, nums[mid] <= nums[right]:
            # we KNOW the pivot must be at mid or to the left of mid:
            # if nums[mid] <= nums[right], we KNOW that the pivot was not encountered
            # to the right of middle, because that means the values would wrap around
            # and become smaller (which is caught in the above if statement).
            # this leaves the possible pivot point to be at index <= mid.
                
            # example: [8,9,1,2,3,4,5,6,7]
            # in the first iteration, when we left with mid index = 4, right index = 9.
            # if nums[mid] <= nums[right], we know the numbers continued increasing to
            # the right of mid, so they never reached the pivot and wrapped around.
            # therefore, we know the pivot must be at index <= mid.

            # we know that nums[mid] <= nums[right].
            # therefore, we know it is possible for the mid index to store a smaller
            # value than at least one other index in the list (at right), so we do
            # not discard it by doing right = mid - 1. it still might have the minimum value.
            right = mid

    # at this point, left and right converge to a single index (for minimum value) since
    # our if/else forces the bounds of left/right to shrink each iteration:

    # when left bound increases, it does not disqualify a value
    # that could be smaller than something else (we know nums[mid] > nums[right],
    # so nums[right] wins and we ignore mid and everything to the left of mid).

    # when right bound decreases, it also does not disqualify a
    # value that could be smaller than something else (we know nums[mid] <= nums[right],
    # so nums[mid] wins and we keep it for now).

    # so we shrink the left/right bounds to one value,
    # without ever disqualifying a possible minimum
    return nums[left]

if __name__ == "__main__":
    #Input: nums = [3,4,5,1,2]
    #Output: 1
    #Explanation: The original array was [1,2,3,4,5] rotated 3 times.
    nums = [3,4,5,1,2]
    print(findMin(nums))

### Uncommented concise solution
from typing import List

def findMin(nums: List[int]) -> int:
    left, right = 0, len(nums)-1
    while left < right:
        mid = left + (right - left) // 2            
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    return nums[left]

if __name__ == "__main__":
    #Input: nums = [3,4,5,1,2]
    #Output: 1
    #Explanation: The original array was [1,2,3,4,5] rotated 3 times.
    nums = [3,4,5,1,2]
    print(findMin(nums))

fun findMin(nums: IntArray): Int {
    var left = 0
    var right = nums.size - 1
    while (left < right) {
        //var mid = (right + left) / 2
        var mid = left + (right - left) / 2
        if (nums[mid] >= nums[left] && nums[mid] > nums[right]) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left]
}

fun main(args: Array<String>) {
    //Input: nums = [3,4,5,1,2]
    //Output: 1
    //Explanation: The original array was [1,2,3,4,5] rotated 3 times.
    val nums = intArrayOf(3,4,5,1,2)
    println(findMin(nums))
}

⬆️ Back to Top

LC-33:Search in Rotated Sorted Array Solution 1

Solution Explanation:

Binary Search Algorithm
=================================================================================================================================================================
Idea:
--------------------------
We have an ascending array, which is rotated at some pivot.
Let's call the rotation the inflection point. (IP)
One characteristic the inflection point holds is: arr[IP] > arr[IP + 1] and arr[IP] > arr[IP - 1]
So if we had an array like: [7, 8, 9, 0, 1, 2, 3, 4] the inflection point, IP would be the number 9.

One thing we can see is that values until the IP are ascending. And values from IP + 1 until end are also ascending (binary search, wink, wink).
Also the values from [0, IP] are always bigger than [IP + 1, n].

Intuition:
--------------------------
We can perform a Binary Search.
If A[mid] is bigger than A[left] we know the inflection point will be to the right of us, meaning values from a[left]...a[mid] are ascending.

So if target is between that range we just cut our search space to the left.
Otherwise go right.

The other condition is that A[mid] is not bigger than A[left] meaning a[mid]...a[right] is ascending.
In the same manner we can check if target is in that range and cut the search space correspondingly.

Complexity Analysis:

Time Complexity : O(log(N))
========================
Same as Binary Search O(log(N))

Space Complexity : O(1)
========================

from typing import List

def search(nums: List[int], target: int) -> int:
    n = len(nums)
    left, right = 0, n - 1
    if n == 0: return -1
        
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target: return mid
            
        # inflection point to the right. Left is strictly increasing
        if nums[mid] >= nums[left]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
                    
        # inflection point to the left of me. Right is strictly increasing
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
            
        return -1

if __name__ == "__main__":
    #Input: nums = [4,5,6,7,0,1,2], target = 0
    #Output: 4
    nums = [4,5,6,7,0,1,2]
    target = 0
    print(search(nums, target))

fun search(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            nums[mid] == target -> return mid
            nums[left] <= nums[mid] -> if (target in nums[left] .. nums[mid]) right = mid - 1 else left = mid + 1
            nums[mid] <= nums[right] -> if (target in nums[mid] .. nums[right]) left = mid + 1 else right = mid - 1
        }
    }
    return -1
}

fun main(args: Array<String>) {
    //Input: nums = [4,5,6,7,0,1,2], target = 0
    //Output: 4
    val nums = intArrayOf(4,5,6,7,0,1,2)
    val target = 0
    println(search(nums, target))
}

⬆️ Back to Top

LC-11:Container With Most Water

Formal Proof than an O(N) solution exists:

Formal Proof than an O(N) solution exists:
=================================================================================================================================================================
Problem Description:
Condition: We have two pointers at i & j, suppose h[i] <= h[j].
Goal to Prove: If there is a better answer within the sub-range of [i, j], then the range [i + 1, j] must contain that optimal sub-range. (This doesn't mean range [i, j - 1] can't contain it, we just want to prove range [i + 1, j] will contain it).

Proof:
Since we assume there is a better answer in the sub-range of [i, j], then this optimal range must be contained by either [i + 1, j] or [i, j - 1], or both.

Let's assume [i + 1, j] doesn't contain the optimal range, but [i, j - 1] contains it. Then this means two things:

the optimal range is not in [i + 1, j - 1], otherwise, [i + 1, j] will contain it.
The optimal range contains the block [i, i + 1] (since this is the part which exists in [i, j - 1] but not in [i+1, j]).
However, notice that, len(i, j - 1) < len(i, j), and in the range [i, j], the area is constrained by the height of h[i] (even in the case h[i] == h[j]). Thus, in the range [i, j - 1], even all pillar are no shorter than h[j], the maximum area is smaller than the area formed by i & j, which contradicts our assumption there is a better answer in the sub-range of [i, j]. This contradiction suggests [i + 1, j] contains the optimal sub-range, if such sub-range exists.

According to above theorem, we can design the algorithm, whenever h[i] < h[j], we advance the pointer i.

Solution Explanation:

=================================================================================================================================================================
Solution Explanation:
Two Pointers
=================================================================================================================================================================
- O(N) solution which is explained in editorial. Why the solution works needs some thought.
- Use two pointers start and end initialized at 0 and N-1
- Now compute the area implied by these pointers as (end-start) * min (height[start], height[end])
- if height[start] < height[end], start = start + 1 else end = end -1
- Why? Imagine height[start] < height[end]. Then is there any need to compare height[end-1] with height[start]? 
  There is no way we can now get a larger area using height[start] as one of the end points. We should therefore move start.

Complexity Analysis:

Time  : O(N)
========================
We traverse the list containing N elements only once. Each look up in the table costs only O(1) time.

Space : O(1)
========================
The constant space required by the output variable max_water.

from typing import List

def maxArea(height: List[int]) -> int:
    """
    :type height: List[int]
    :rtype: int
    """
    start, end = 0, len(height)-1
    max_water = -1
    while start < end:
        max_water = max(max_water, (end-start)*min(height[start], height[end]))
        if height[start] < height[end]:
            start = start+1
        else:
            end = end-1
    return max_water

if __name__ == "__main__":
    #Input: height = [1,8,6,2,5,4,8,3,7]
    #Output: 49
    #Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. 
    #             In this case, the max area of water (blue section) the container 
    #             can contain is 49.
    height = [1,8,6,2,5,4,8,3,7]
    print(maxArea(height))

fun maxArea(height: IntArray): Int {    
    val ans:MutableList<List<Int>> = mutableListOf()
    var start = 0
    var end = height.size - 1
    var maxWater = -1
    while (start < end) {
        maxWater = maxOf(maxWater, (end-start)*minOf(height[start], height[end]))
        if (height[start] < height[end]) {
            start++
        } else {
            end--
        }
    }
    return maxWater
}

fun main(args: Array<String>) {
    //Input: height = [1,8,6,2,5,4,8,3,7]
    //Output: 49
    //Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. 
    //             In this case, the max area of water (blue section) the container 
    //             can contain is 49.
    val height = intArrayOf(1,8,6,2,5,4,8,3,7)
    println(maxArea(height))
}

⬆️ Back to Top

Bit Manipulation

#	Title	url	Time	Space	Difficulty	Tag
0371	Sum of Two Integers	https://leetcode.com/problems/sum-of-two-integers/	O(1)	O(1)	Easy	LintCode
0191	Number of 1 Bits	https://leetcode.com/problems/number-of-1-bits/	O(1)	O(1)	Easy
0338	Counting Bits	https://leetcode.com/problems/counting-bits/	O(n)	O(n)	Medium
0268	Missing Number	https://leetcode.com/problems/missing-number/	O(n)	O(1)	Medium	LintCode
0190	Reverse Bits	https://leetcode.com/problems/reverse-bits/	O(1)	O(1)	Easy

Dynamic Programming

#	Title	url	Time	Space	Difficulty	Tag	Note
0070	Climbing Stairs	https://leetcode.com/problems/climbing-stairs/	O(logn)	O(1)	Easy		DP and Fibonacci Sequence
0322	Coin Change	https://leetcode.com/problems/coin-change/	O(n k)*	O(k)	Medium
0300	Longest Increasing Subsequence (LIS)	https://leetcode.com/problems/longest-increasing-subsequence/	O(nlogn)	O(n)	Medium	CTCI, LintCode	Patience Sorting using Binary Search, DP
1143	Longest Common Subsequence (LCS)	https://leetcode.com/problems/longest-common-subsequence/	O(m n)*	O(min(m, n))	Medium
0139	Word Break	https://leetcode.com/problems/word-break/	O(n l^2)*	O(n)	Medium
0377	Combination Sum IV	https://leetcode.com/problems/combination-sum-iv/	O(nlogn + n t)*	O(t)	Medium
0198	House Robber	https://leetcode.com/problems/house-robber/	O(n)	O(1)	Easy
0213	House Robber II	https://leetcode.com/problems/house-robber-ii/	O(n)	O(1)	Medium
0091	Decode Ways	https://leetcode.com/problems/decode-ways/	O(n)	O(1)	Medium
0062	Unique Paths	https://leetcode.com/problems/unique-paths/	O(m n)*	O(m + n)	Medium
0055	Jump Game	https://leetcode.com/problems/jump-game/	O(n)	O(1)	Medium

LC-300:Longest Increasing Subsequence

Solution Explanation:

=================================================================================================================================================================
Approach 1: Patience Sorting using Binary Search
=================================================================================================================================================================
This algorithm is actually Patience sorting. 
It might be easier for you to understand how it works if you think about it as piles of cards instead of tails.
The number of piles is the length of the longest subsequence.
For more info see Princeton lecture.

1) Initially, there are no piles. The first card dealt forms a new pile consisting of the single card.
2) Each subsequent card is placed on the leftmost existing pile whose top card has a value greater 
   than or equal to the new card's value, or to the right of all of the existing piles, thus forming a new pile.
3) When there are no more cards remaining to deal, the game ends.

Detailed Algorithm:
-----------------------
piles is an array storing the smallest tail of all increasing subsequences with length i+1 in piles[i].
For example, say we have nums = [4,5,6,3], then all the available increasing subsequences are:

len = 1   :      [4], [5], [6], [3]   => piles[0] = 3
len = 2   :      [4, 5], [5, 6]       => piles[1] = 5
len = 3   :      [4, 5, 6]            => piles[2] = 6
We can easily prove that piles is a increasing array. Therefore it is possible to do a binary search in piles array to find the one needs update.

Each time we only do one of the two:

(1) if num is larger than all piles, append it, increase the size by 1
(2) if piles[i-1] < num <= piles[i], update piles[i]
(3) Doing so will maintain the piles invariant. The the final answer is just the size.


-----------------------
References:
https://en.wikipedia.org/wiki/Patience_sorting
Priceton Lecture on LIS: https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf

=================================================================================================================================================================
Approach 2: DP
=================================================================================================================================================================
1) Check the base case, if nums has size less than or equal to 1, then return length of nums
2) Create a 'dp' array of size nums.length to track the longest sequence length
3) Fill each position with value 1 in the array
4) Mark one pointer at i. For each i, start from j=0.
   4.1.1) If, nums[j] < nums[i], it means next number contributes to increasing sequence. 
      4.1.1.1) But increase the value only if it results in a larger value of the sequence than dp[i].
               It is possible that dp[i] already has larger value from some previous j'th iteration.
5) Find the maximum length from the array that we just generated.

-----------------------
References:
https://www.youtube.com/watch?v=CE2b_-XfVDk

Interview Tips:

NOTES: In an Interview Situation - Choose Approach 1 ( Patience Sorting using Binary Search ) over Approach 2 ( DP ),
       since it is an O(N*log(N)) TC [ DP is worse off at O(N^2) ].

Complexity Analysis:

=================================================================================================================================================================
Approach 1: Patience Sorting using Binary Search
=================================================================================================================================================================
TIME COMPLEXITY : O(N*log(N))
SPACE COMPLEXITY : O(N)
=================================================================================================================================================================
Approach 2: DP
=================================================================================================================================================================
TIME COMPLEXITY : O(N^2)
SPACE COMPLEXITY : O(N)

#=================================================================================================================================================================
#Approach 1 ( Patience Sorting using Binary Search ) ... answer for the Follow-Up question
#TC: O(N*log(N))
#SC: O(N)
#=================================================================================================================================================================
from typing import List

def binary_search(nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def lengthOfLIS(nums: List[int]) -> int:
    piles = []
    for num in nums:
        if not piles or num > piles[-1]:
            piles.append(num)
        else:
            pos = binary_search(piles, num)
            piles[pos] = num
    return len(piles)

def lengthOfLIS(nums: List[int]) -> int:
    if len(nums) == 0:
        return 0
    piles = [0] * len(nums)
    longest = 0
    for num in nums:
        i, j = 0, longest
        while i != j:
            m = (i + j) // 2
            if piles[m] < x:
                i = m + 1
            else:
                j = m
        piles[i] = x
        longest = max(i + 1, longest)
    return longest

if __name__ == "__main__":
    #Input: nums = [10,9,2,5,3,7,101,18]
    #Output: 4
    #Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
    nums = [10,9,2,5,3,7,101,18]
    print(lengthOfLIS(nums))
	
#=================================================================================================================================================================
#Approach 2 ( DP )
#TC: O(N^2)
#SC: O(N)
#=================================================================================================================================================================
from typing import List

def lengthOfLIS(nums: List[int]) -> int:
    if len(nums) == 0:
        return 0
    nums_length = len(nums)
    dp = [1] * nums_length
    longest = 1
    for i in range(nums_length):
        for j in range(i):
            if nums[i] < nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
        longest = max(longest, dp[i])
    return longest

if __name__ == "__main__":
    #Input: nums = [10,9,2,5,3,7,101,18]
    #Output: 4
    #Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
    nums = [10,9,2,5,3,7,101,18]
    print(lengthOfLIS(nums))

//=================================================================================================================================================================
//Approach 1 ( Patience Sorting using Binary Search ) ... answer for the Follow-Up question
//TC: O(N*log(N))
//SC: O(N)
//=================================================================================================================================================================
fun binarySearch(nums: IntArray, target: Int): Int {
    var lo = 0
    var hi = nums.size
    while (lo < hi) {
        val mid = (lo + hi) / 2
        if (nums[mid] < target) {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

fun lengthOfLIS(nums: IntArray): Int {
    // sanity check
    if (nums.isEmpty()) return 0

    var piles: MutableList<Int> = mutableListOf()
    for (num in nums) {
        if ( num > piles?.lastOrNull() ?: -1 ) {
            piles.add(num)
        } else {
            val pos = binarySearch(piles.toIntArray(), num)
            piles[pos] = num
        }
    }
    return piles.size
}

fun lengthOfLIS(nums: IntArray): Int {
    // sanity check
    if (nums.isEmpty()) return 0
    val piles = IntArray(nums.size)
    var longest = 0
    for (x in nums) {
        var i = 0
        var j = longest
        while (i != j) {
            var m = (i + j) / 2
            if (piles[m] < x) {
                i = m + 1
            } else {
                j = m
            }
        }
        piles[i] = x
        if (i == longest) ++longest
    }
    return longest
}

fun main(args: Array<String>) {
    //Input: nums = [10,9,2,5,3,7,101,18]
    //Output: 4
    //Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
    val nums = intArrayOf(10,9,2,5,3,7,101,18)
    println(lengthOfLIS(nums))
}

//=================================================================================================================================================================
//Approach 2 ( DP )
//TC: O(N^2)
//SC: O(N)
//=================================================================================================================================================================
fun lengthOfLIS(nums: IntArray): Int {
    // sanity check
    if (nums.isEmpty()) return 0

    val nums_length = nums.size

    val dp = IntArray(nums_length) { 1 }
    var longest = 1

    for (i in 0 until nums_length) {
        for (j in 0 until i) {
            if (nums[i] > nums[j]) {
                dp[i] = maxOf(dp[i], dp[j] + 1)
            }
        }
        longest = maxOf(longest, dp[i])
    }
    return longest
}

fun main(args: Array<String>) {
    //Input: nums = [10,9,2,5,3,7,101,18]
    //Output: 4
    //Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
    val nums = intArrayOf(10,9,2,5,3,7,101,18)
    println(lengthOfLIS(nums))
}

⬆️ Back to Top

LC-1143:Longest Common Subsequence

Solution Explanation:

Solution Approach:
=================================================================================================================================================================
DP with Memoization and 1D array for "Space Optimization"
-----------------------------------------------------------

Find LCS;
Let X be “XMJYAUZ” and Y be “MZJAWXU”. The longest common subsequence between X and Y is “MJAU”. 
The following table shows the lengths of the longest common subsequences between prefixes of X and Y.
The ith row and jth column shows the length of the LCS between X_{1..i} and Y_{1..j}.

+-------+---+---+---+---+---+---+---+---+
|       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|       +---+---+---+---+---+---+---+---+
|       | 0 | M | Z | J | A | W | X | U |
+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 |*0*| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+---+
| 1 | X | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+---+
| 2 | M | 0 |*1*| 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+---+
| 3 | J | 0 | 1 | 1 |*2*| 2 | 2 | 2 | 2 |
+---+---+---+---+---+---+---+---+---+---+
| 4 | Y | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 |
+---+---+---+---+---+---+---+---+---+---+
| 5 | A | 0 | 1 | 1 | 2 |*3*| 3 | 3 | 3 |
+---+---+---+---+---+---+---+---+---+---+
| 6 | U | 0 | 1 | 1 | 2 | 3 | 3 | 3 |*4*|
+---+---+---+---+---+---+---+---+---+---+
| 7 | Z | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 4 |
+---+---+---+---+---+---+---+---+---+---+

References:
-----------------
https://en.m.wikipedia.org/wiki/Longest_common_subsequence_problem
https://www.ics.uci.edu/~eppstein/161/960229.html

Complexity Analysis:

TIME COMPLEXITY : O(M*N)
SPACE COMPLEXITY : O(MIN(M,N))

where:
------
M = length of string text1
N = length of string text2

#Q & A:
#---------------
#Q1: What is the difference between [[0] * m * n] and [[0] * m for _ in range(n)]? 
#    Why does the former update all the rows of that column when I try to update one particular cell ?
#A1: [[0] * m * n] creates n references to the exactly same list objet: [0] * m; 
#    In contrast: [[0] * m for _ in range(n)] creates n different list objects that have same value of [0] * m.
#
def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = map(len, (text1, text2))
    if m < n:
        return self.longestCommonSubsequence(text2, text1)
    dp = [0] * (n + 1)
    for c in text1:
        prevRow, prevRowPrevCol = 0, 0
        for j, d in enumerate(text2):
            prevRow, prevRowPrevCol = dp[j + 1], prevRow
            dp[j + 1] = prevRowPrevCol + 1 if c == d else max(dp[j], prevRow)
    return dp[-1]

if __name__ == "__main__":
    #Input: text1 = "abcde", text2 = "ace" 
    #Output: 3  
    #Explanation: The longest common subsequence is "ace" and its length is 3.
    text1 = "abcde"
    text2 = "ace"
    print(longestCommonSubsequence(text1,text2))

fun longestCommonSubsequence(text1: String, text2: String): Int {
    val m = text1.length
    val n = text2.length
    if (m < n) {
        return longestCommonSubsequence(text2, text1);
    }
    val dp = IntArray(n+1)
    for (c in text1) {
        var prevRow = 0
        var prevRowPrevCol = 0
        for ((j, d) in text2.withIndex()) {
            prevRow = dp[j + 1]
            prevRowPrevCol = prevRow
            dp[j + 1] = if (c.equals(d)) prevRowPrevCol + 1 else maxOf(dp[j], prevRow)
        }
    }
    return dp.last()
}

fun main(args: Array<String>) {
    //Input: text1 = "abcde", text2 = "ace" 
    //Output: 3  
    //Explanation: The longest common subsequence is "ace" and its length is 3.
    val text1 = "abcde"
    val text2 = "ace"
    println(longestCommonSubsequence(text1,text2))
}

⬆️ Back to Top

Graph

#	Title	url	Time	Space	Difficulty	Tag	Note
0133	Clone Graph	https://leetcode.com/problems/clone-graph/	O(n)	O(n)	Medium
0207	Course Schedule	https://leetcode.com/problems/course-schedule/	O(\|V\| + \|E\|)	O(\|E\|)	Medium		Topological Sort
0417	Pacific Atlantic Water Flow	https://leetcode.com/problems/pacific-atlantic-water-flow/	O(m * n)	O(m * n)	Medium
0200	Number of Islands	https://leetcode.com/problems/number-of-islands/	O(m * n)	O(m * n)	Medium		BFS, DFS, Union Find
0128	Longest Consecutive Sequence	https://leetcode.com/problems/longest-consecutive-sequence/	O(n)	O(n)	Hard		Tricky
0269	Alien Dictionary	https://leetcode.com/problems/alien-dictionary/	O(n)	O(1)	Hard	🔒	Topological Sort, BFS, DFS
0261	Graph Valid Tree	https://leetcode.com/problems/graph-valid-tree/	O(\|V\| + \|E\|)	O(\|V\| + \|E\|)	Medium	🔒
0323	Number of Connected Components in an Undirected Graph	https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/	O(n)	O(n)	Medium	🔒	Union Find

LC-417:Pacific Atlantic Water Flow

Solution Explanation:

=================================================================================================================================================================
Solution Approach:
=================================================================================================================================================================
In a naive approach, we would have to consider each cell and find if it is reachable to both the oceans by checking if it is able to reach - 
1) top or left edge(atlantic) and, 
2) bottom or right edge (pacific). This would take about O((mn)^2), which is not efficient.


We can observe that there are these cells which can reach -

 - None
 - Pacific
 - Atlantic
 - Both Pacific and Atlantic

We need only the cells satisfying the last condition above ( i.e., "Both Pacific and Atlantic" ).

- Now, if we start from the cells connected to altantic ocean and visit all cells having height greater than current cell 
(water can only flow from a cell to another one with height equal or lower), we are able to reach some subset of cells (let's call them A).

- Next, we start from the cells connected to pacific ocean and repeat the same process, we find another subset (let's call this one B).

- The final answer we get will be the intersection of sets A and B (A ∩ B).

So, we just need to iterate from edge cells, find cells reachable from atlantic (set A), 
cells reachable from pacific (set B) and return their intersection.

This can be done using DFS or BFS graph traversals.

Complexity Analysis:

For both DFS and BFS graph traversal approaches:

Time Complexity : O(M*N), in worst case, all cells are reachable to both oceans and would be visited twice. This case can occur when all elements are equal.
Space Complexity : O(M*N), to mark the atlantic and pacific visited cells.

# Approach 1) DFS Traversal
# ----------------------------------------
from typing import List

directions = [(1,0),(-1,0),(0,1),(0,-1)]

def dfs(grid: List[List[int]], i: int, j: int, visited: List[bool], m: int, n: int) -> None:
    # when dfs called, meaning its caller already verified this point 
    visited[i][j] = True
    for dir in directions:
        x, y = i + dir[0], j + dir[1]
        if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or grid[x][y] < grid[i][j]:
            continue
        dfs(grid, x, y, visited, m, n)

def pacificAtlantic(heights: List[List[int]]) -> List[List[int]]:
    if not heights: return []
    m = len(heights)
    n = len(heights[0])
    p_visited = [[False for _ in range(n)] for _ in range(m)]    
    a_visited = [[False for _ in range(n)] for _ in range(m)]
    result = []  

    for i in range(m):
        # p_visited[i][0] = True
        # a_visited[i][n-1] = True
        dfs(heights, i, 0, p_visited, m, n)
        dfs(heights, i, n-1, a_visited, m, n)
    for j in range(n):
        # p_visited[0][j] = True
        # a_visited[m-1][j] = True
        dfs(heights, 0, j, p_visited, m, n)
        dfs(heights, m-1, j, a_visited, m, n)            

    for i in range(m):
        for j in range(n):
            if p_visited[i][j] and a_visited[i][j]:
                result.append([i,j])
    return result

if __name__ == "__main__":
    #Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
    #Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
    heights = [[1,2,2,3,5],
               [3,2,3,4,4],
               [2,4,5,3,1],
               [6,7,1,4,5],
               [5,1,1,2,4]]
    print(pacificAtlantic(heights))
            
# Approach 2) BFS Traversal
# ----------------------------------------
from collections import deque
from typing import List

def pacificAtlantic(heights: List[List[int]]) -> List[List[int]]:
    if not heights:
        return []
        
    rows, cols = len(heights), len(heights[0])
    p_visited, a_visited = set(), set()
    a_queue, p_queue = [], []

    def bfs(queue, visited):
        directions = ((1,0), (-1,0), (0,1),(0,-1))
        q = deque(queue)
            
        while q:
            i,j = q.popleft()
            if (i,j) in visited:
                continue
            visited.add((i,j))
                
            for direction in directions:
                x, y = i + direction[0], j + direction[1]
                if  0 <= x < rows and 0<= y < cols and heights[x][y] >= heights[i][j]:
                    q.append((x,y))
        
    for i in range(rows):
        a_queue.append((i, cols-1))
        p_queue.append((i,0))
            
    for j in range(cols):
        a_queue.append((rows-1, j))
        p_queue.append((0,j))

    bfs(a_queue, a_visited)
    bfs(p_queue, p_visited)
    return list(a_visited & p_visited)


if __name__ == "__main__":
    #Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
    #Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
    heights = [[1,2,2,3,5],
               [3,2,3,4,4],
               [2,4,5,3,1],
               [6,7,1,4,5],
               [5,1,1,2,4]]
    print(pacificAtlantic(heights))

// Approach 1) DFS Traversal
// ----------------------------------------
val dirs = arrayOf(intArrayOf(0,1), 		// Right ( East  )
                   intArrayOf(0,-1),            // Left  ( West  )
                   intArrayOf(1,0),             // Down  ( South )
                   intArrayOf(-1,0))            // Up    ( North )

private fun dfs(grid: Array<IntArray>, height: Int, i: Int, j: Int, visited: Array<BooleanArray>) {
    if(i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] < height || visited[i][j]) return
        
    visited[i][j] = true
        
    dirs.forEach { dir -> 
        dfs(grid, grid[i][j], dir[0] + i, dir[1] + j, visited)
    }
}

fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
    if(heights.size == 0) return emptyList()
    val result = mutableListOf<List<Int>>()
        
    val pacific = Array(heights.size) { BooleanArray(heights[0].size) }
    val atlantic = Array(heights.size) { BooleanArray(heights[0].size) }
        
    for(i in 0 until heights.size) {
        dfs(heights, Integer.MIN_VALUE, i, 0, pacific)
        dfs(heights, Integer.MIN_VALUE, i, heights[0].size - 1, atlantic)
    }
        
    for(i in 0 until heights[0].size) {
        dfs(heights, Integer.MIN_VALUE, 0, i, pacific)
        dfs(heights, Integer.MIN_VALUE, heights.size - 1, i, atlantic)
    }
        
    for(i in 0 until heights.size) {
        for(j in 0 until heights[0].size) {
            if(atlantic[i][j] && pacific[i][j]) result.add(listOf(i, j))
        }
    }
        
    return result
}

fun main(args: Array<String>) {
    //Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
    //Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
    val heights = arrayOf(intArrayOf(1,2,2,3,5),
                          intArrayOf(3,2,3,4,4),
                          intArrayOf(2,4,5,3,1),
                          intArrayOf(6,7,1,4,5),
                          intArrayOf(5,1,1,2,4))
    println(pacificAtlantic(heights))
}

// Approach 2) BFS Traversal
import java.util.LinkedList

private fun canFlow(matrix: Array<IntArray>, current: IntArray, neighbor: IntArray) =
    matrix[current[0]][current[1]] <= matrix[neighbor[0]][neighbor[1]]

private fun bfs(matrix: Array<IntArray>, queue: LinkedList<IntArray>, visited: Array<BooleanArray>, result: Array<BooleanArray>) {
    while(!queue.isEmpty()) {
        val current = queue.poll()
        val x = current[0]
        val y = current[1]
            
        visited[x][y] = true
        result[x][y] = true
            
        val top = intArrayOf(x - 1, y)
        if(top[0] >= 0 && !visited[top[0]][top[1]] && canFlow(matrix, current, top)) {
            queue.offer(top)
        }
            
        val bottom = intArrayOf(x + 1, y)
        if(bottom[0] <= matrix.size - 1 && !visited[bottom[0]][bottom[1]] && canFlow(matrix, current, bottom)) {
            queue.offer(bottom)
        }
            
        val left = intArrayOf(x, y - 1)
        if(left[1] >= 0 && !visited[left[0]][left[1]] && canFlow(matrix, current, left)) {
            queue.offer(left)
        }
            
        val right = intArrayOf(x, y + 1)
        if(right[1] <= matrix[0].size - 1 && !visited[right[0]][right[1]] && canFlow(matrix, current, right)) {
            queue.offer(right)
        }
    }
}

private fun getResult(matrix: Array<IntArray>, startEdges: List<IntArray>) : Array<BooleanArray> {
    val queue = LinkedList(startEdges)
    val visited = Array<BooleanArray>(matrix.size) { BooleanArray(matrix[0].size) { false } }
    val result = Array<BooleanArray>(matrix.size) { BooleanArray(matrix[0].size) { false } }
    bfs(matrix, queue, visited, result)
    return result
}
    
private fun pacificEdges(matrix: Array<IntArray>) : List<IntArray> {
    val result = mutableListOf<IntArray>()
    (0 until matrix.size).forEach { result.add(intArrayOf(it, 0)) }
    (0 until matrix[0].size).forEach { result.add(intArrayOf(0, it)) }
    return result
}
    
private fun atlanticEdges(matrix: Array<IntArray>) : List<IntArray> {
    val result = mutableListOf<IntArray>()
    (0 until matrix.size).forEach { result.add(intArrayOf(it, matrix[0].size - 1)) }
    (0 until matrix[0].size).forEach { result.add(intArrayOf(matrix.size - 1, it)) }
    return result
}

fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
    //val result = mutableListOf<IntArray>()
    val result = mutableListOf<List<Int>>()
    if(heights.isEmpty()) return result
        
    val pacificResult = getResult(heights, pacificEdges(heights))
    val atlanticResult = getResult(heights, atlanticEdges(heights))
        
    (0 until heights.size).forEach { x ->
        (0 until heights[0].size).forEach { y ->
            if(pacificResult[x][y] && atlanticResult[x][y]) {
                //result.add(intArrayOf(x, y))
                result.add(listOf(x, y))
            }
        }
    }
        
    return result
}

fun main(args: Array<String>) {
    //Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
    //Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
    val heights = arrayOf(intArrayOf(1,2,2,3,5),
                          intArrayOf(3,2,3,4,4),
                          intArrayOf(2,4,5,3,1),
                          intArrayOf(6,7,1,4,5),
                          intArrayOf(5,1,1,2,4))
    println(pacificAtlantic(heights))
}

⬆️ Back to Top

LC-128:Longest Consecutive Sequence

Solution Explanation:

=================================================================================================================================================================
Solution Approach:
=================================================================================================================================================================
DFS

We can think this is a undirectional graph: every number i is connected with its two adjacent numbers i-1, i+1.
So that we can start from a number in the input (convert input to be a set so that look up a number whether in the set has O(1) complexity),
use DFS to traverse the whole graph.

Visited numbers are removed from the set so that we don't revisit one number twice.

Complexity Analysis:

Time Complexity   : O(N)
Space Complexity  : O(N)

from typing import List, Set

def dfs(numSet: Set[int], root: int, size: List[int]):
    if root-1 in numSet:
        size[0]+= 1
        numSet.remove(root-1) #mark it as visited when check the neighbor
        dfs(numSet, root-1, size)
    if root+1 in numSet:
        size[0]+= 1
        numSet.remove(root+1)
        dfs(numSet, root+1, size)

def longestConsecutive(nums: List[int]) -> int:
    if not nums:
        return 0
        
    numSet = set(nums)
    max_length = 1
    while numSet:
        size=[1]
        current= numSet.pop()
        dfs(numSet, current, size)
        max_length= max(max_length, size[0])
    return max_length

if __name__ == "__main__":
    #Input: nums = [100,4,200,1,3,2]
    #Output: 4
    #Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
    nums = [100,4,200,1,3,2]
    print(longestConsecutive(nums))

fun <T> MutableSet<T>.pop(): T? = this.first().also{this.remove(it)}

fun dfs(numSet: MutableSet<Int>, root: Int, size: IntArray) {
    if (root-1 in numSet) {
        size[0] += 1
        numSet.remove(root-1) //mark it as visited when check the neighbor
        dfs(numSet, root-1, size)
    }
    if (root+1 in numSet) {
        size[0] += 1
        numSet.remove(root+1)
        dfs(numSet, root+1, size)
    }
}

fun longestConsecutive(nums: IntArray): Int {
    if (nums.isEmpty()) return 0
        
    val numSet = nums.toMutableSet()
    var maxLength = 1

    while (!numSet.isEmpty()) {
        val size = intArrayOf(1)
        val current = numSet.pop()
        dfs(numSet, current!!, size)
        maxLength= maxOf(maxLength, size[0])
    }
    return maxLength       
}

fun main(args: Array<String>) {
    //Input: nums = [100,4,200,1,3,2]
    //Output: 4
    //Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
    val nums = intArrayOf(100,4,200,1,3,2)
    println(longestConsecutive(nums))
}

⬆️ Back to Top

LC-323:Number of Connected Components in an Undirected Graph

Solution Explanation:

BFS
---------
- Start from index 0 to n.
- For each index : 
  - use BFS to find all it’s related numbers
  - append them to the visited set
  - if this index has no more related numbers then increment count ( count = count + 1 )
    and 
  - start from next index
  - note that if the index is in visited set. we skip to next index

Complexity Analysis:

Time complexity: O(2N)

Build graph will take O(N) and traversal all number will take O(N). In total is O(2N) where N is the given as the size of the index.

Space Complexity  : O(N)

#BFS
from collections import defaultdict, deque
from typing import List

def countComponents(n: int, edges: List[List[int]]) -> int:
    dist = defaultdict(list)
    for source, target in edges:
        dist[source].append(target)
        dist[target].append(source)
    count = 0
    visited = set()
    queue = deque()
    for x in range(n):
        if x in visited:
            continue
        queue.append(x)
        while queue:
            source=queue.popleft()
            if source in visited:
                continue
            visited.add(source)
            for target in dist[source]:
                queue.append(target)
        count+=1
    return count

fun countComponents(n: Int, edges: Array<IntArray>): Int {
    val dist = mutableMapOf<Int, MutableList<Int>>()
    edges.forEach{value->
        var source = value[0]
        var target = value[1]
        dist.get(source)?.add(target) 
        dist.get(target)?.add(source) 
    }
    var count = 0
    val visited = mutableSetOf<Int>()
    val queue = mutableListOf<Int>()
    for (x in 0 until n) {
        if (visited.contains(x)) continue
        queue.add(x)
        while (queue.isNotEmpty()) {
            val source = queue.removeAt(0)
            if (visited.contains(source)) continue
            visited.add(source)
            dist.get(source)?.forEach{v->
                queue.add(v)
            }
        }
        count++
    }
    return count
}

fun main(args: Array<String>) {
    //Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]
    //
    //0          3
    //|          |
    //1 --- 2    4 
    //
    //Output: 2
    val n = 5
    val edges = arrayOf(intArrayOf(0,1),
                        intArrayOf(1,2),
                        intArrayOf(3,4))
    println(countComponents(n, edges))
}

⬆️ Back to Top

Interval

#	Title	url	Time	Space	Difficulty	Tag	Note
0057	Insert Interval	https://leetcode.com/problems/insert-interval/	O(n)	O(1)	Hard
0056	Merge Intervals	https://leetcode.com/problems/merge-intervals/	O(nlogn)	O(1)	Hard
0435	Non-overlapping Intervals	https://leetcode.com/problems/non-overlapping-intervals/	O(nlogn)	O(1)	Medium		Line Sweep
0252	Meeting Rooms	https://leetcode.com/problems/meeting-rooms/	O(nlogn)	O(n)	Easy	🔒
0253	Meeting Rooms II	https://leetcode.com/problems/meeting-rooms-ii/)	O(nlogn)	O(n)	Medium	🔒

LC-435:Non-overlapping Intervals

Solution Explanation:

=================================================================================================================================================================
Solution Approach:
Greedy Algorithm
=================================================================================================================================================================
A classic greedy case: interval scheduling problem.

The heuristic is: always pick the interval with the earliest end time. Then you can get the maximal number of non-overlapping intervals. (or minimal number to remove).
This is because, the interval with the earliest end time produces the maximal capacity to hold rest intervals.
E.g. Suppose current earliest end time of the rest intervals is x. Then available time slot left for other intervals is [x:]. If we choose another interval with end time y, then available time slot would be [y:]. Since x ≤ y, there is no way [y:] can hold more intervals then [x:]. Thus, the heuristic holds.

Therefore, we can sort interval by ending time and key track of current earliest end time. Once next interval's start time is earlier than current end time, then we have to remove one interval. Otherwise, we update earliest end time.

Complexity Analysis:

TC: O(N*log(N))

Time complexity is O(NlogN) as sort overwhelms greedy search.

SC: O(1)

from typing import List

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    end, cnt = float('-inf'), 0
    for s, e in sorted(intervals, key=lambda x: x[1]):
        if s >= end: 
            end = e
        else: 
            cnt += 1
    return cnt

if __name__ == "__main__":
    #Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
    #Output: 1
    #Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
    intervals = [[1,2],[2,3],[3,4],[1,3]]
    print(eraseOverlapIntervals(intervals))

fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
    if (intervals.isEmpty()) return 0
    
    // sorting with end pos
    intervals.sortWith(Comparator { a, b -> a[1].compareTo(b[1]) })

    var prevEnd = intervals[0][1]
    var removals = 0

    // greedy
    for (i in 1..intervals.size - 1) {
        if (intervals[i][0] < prevEnd)
            removals++
        else
            prevEnd = intervals[i][1]
    }

    return removals        
}

fun main(args: Array<String>) {
    //Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
    //Output: 1
    //Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
    val intervals = arrayOf(intArrayOf(1,2),
                            intArrayOf(2,3),
                            intArrayOf(3,4),
                            intArrayOf(1,3))
    println(eraseOverlapIntervals(intervals)))
}

⬆️ Back to Top

Linked List

#	Title	url	Time	Space	Difficulty	Note
0206	Reverse Linked List	https://leetcode.com/problems/reverse-linked-list/	O(n)	O(1)	Easy
0141	Linked List Cycle	https://leetcode.com/problems/linked-list-cycle/	O(n)	O(1)	Easy
0021	Merge Two Sorted Lists	https://leetcode.com/problems/merge-two-sorted-lists/	O(n)	O(1)	Easy
0023	Merge k Sorted Lists Solution 1	https://leetcode.com/problems/merge-k-sorted-lists/	O(nlogk)	O(1)	Hard	Heap, Divide and Conquer
0019	Remove Nth Node From End of List	https://leetcode.com/problems/remove-nth-node-from-end-of-list/	O(n)	O(1)	Medium
0143	Reorder List	https://leetcode.com/problems/reorder-list/	O(n)	O(1)	Medium

LC-23:Merge k Sorted Lists Solution 1

Data Structure Learning Points - What is a Priority Queue ?

In computer science, a priority queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally 
has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued,
while in other implementations, ordering of elements with the same priority is undefined.

While priority queues are often implemented with heaps, they are conceptually distinct from heaps.
A priority queue is a concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array,
a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.

Interview Note

In an interview situation, use "Approach 2: Merge with Divide And Conquer".
This is what an interviewer expects.

Solution Explanation:

----------------------------------------------------
Approach 1: Compare one-by-one using Priority Queue
----------------------------------------------------

Algorithm

- Compare every k nodes (head of every linked list) and get the node with the smallest value.
- Extend the final sorted linked list with the selected nodes.
- Optimize the comparison process by using a priority queue data structure.

----------------------------------------------------
Approach 2: Merge with Divide And Conquer
----------------------------------------------------

Intuition & Algorithm
----------------------
We don't need to traverse most nodes many times repeatedly

 - Pair up k lists and merge each pair.
 - After the first pairing, k lists are merged into k/2 lists with average 2N/k length,
   then k/4, k/8 and so on.
 - Repeat this procedure until we get the final sorted linked list.

Thus, we'll traverse almost NN nodes per pairing and merging, and repeat this procedure about log2(k) times.
            +------------------------------------------------------------------+
            |  Lists                                                           |
            | +-------+  +-------+  +-------+  +-------+  +-------+  +-------+ |
            | | list0 |  | list1 |  | list2 |  | list3 |  | list4 |  | list5 | |
            | +-------+  +-------+  +-------+  +-------+  +-------+  +-------+ |
            +---|----------/-----------|---------/-----------|---------/-------+
                |         /            |        /            |        /
Merging         |        /             |       /             |       /
   +------------|-------/--------------|------/--------------|------/-----+
   | Lists      |      /               |     /               |     /      |
   |           \|/   \/_              \|/  \/_              \|/  \/_      |
   |         +--*----*---+          +--*---*---+          +--*---*---+    |
   |         |   list0   |          |  list2   |          |   list4  |    |
   |         +-----------+          +----------+          +----------+    |
   +------------|--------------------/----------------------|-------------+
Merging         |        +----------+                       |
   +------------|-------/-----------------------------------|------------+
   | Lists     \|/    \/_                                  \|/           |
   |         +--*-----*---+                               +-*--------+   |
   |         |   list0    |                               |   list4  |   |
   |         +------------+                               +----------+   |
   +------------|---------------------------------------------/----------+
Merging         |        +-----------------------------------+
                |       /
               \|/    \/_
             +--*-----*----+
             |    result   |
             +-------------+

Complexity Analysis:

----------------------------------------------------
Approach 1: Compare one-by-one using Priority Queue
----------------------------------------------------
Complexity Analysis
----------------------------------------------------

Time complexity : where k is the number of linked lists.

	+ The comparison cost will be reduced to O(logk) for every pop and insertion to priority queue.
	+ But finding the node with the smallest value just costs O(1) time.
	+ There are N nodes in the final linked list.

- Space complexity :

	+ O(n) Creating a new linked list costs O(n) space.
	+ O(k) The code above present applies in-place method which cost O(1) space.
	  And the priority queue (often implemented with heaps) costs O(k) space 
	  (it's far less than N in most situations).

----------------------------------------------------
Approach 2: Merge with Divide And Conquer
----------------------------------------------------
Complexity Analysis
----------------------------------------------------

Time complexity : where k is the number of linked lists.

	+ We can merge two sorted linked list in O(n) time where nn is the total number of nodes in two lists.
	+ Sum up the merge process and we can get:

- Space complexity : O(1)

	+ We can merge two sorted linked lists in O(1) space.

import heapq
from queue import PriorityQueue
from typing import List
import unittest

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    @classmethod
    def initList(self, nums):
        if not nums:
            return None
        head = None
        current = None

        for n in nums:
            if not head:
                head = ListNode(n)
                current = head
            else:
                node = ListNode(n)
                current.next = node
                current = node
        return head

    @classmethod
    def linkedListToList(self, head):
        if not head:
            return []

        pointer = head
        sll_list = []
        while pointer:
            sll_list.append(pointer.val)
            pointer = pointer.next
        return sll_list


# https://stackoverflow.com/questions/40205223/priority-queue-with-tuples-and-dicts
class use_only_first:
    def __init__(self, first, second):
        self._first, self._second = first, second

    def __lt__(self, other):
        return self._first < other._first
		
class Solution:

    #----------------------------------------------------
    #Approach 1: Compare one-by-one using Priority Queue
    #----------------------------------------------------
    # Using heapq for Priortiy Queue
    def mergeKListsUsingHeap(self, lists: List[ListNode]) -> ListNode:
	    h = [(l.val, idx) for idx, l in enumerate(lists) if l]
        heapq.heapify(h)
        head = cur = ListNode(None)
        while h:
            val, idx = heapq.heappop(h)
            cur.next = ListNode(val)
            cur = cur.next
            node = lists[idx] = lists[idx].next
            if node:
                heapq.heappush(h, (node.val, idx))
        return head.next
	
	# Using PriorityQueue class
	def mergeKListsUsingPriorityQueue(self, lists: List[ListNode]) -> ListNode:
	    q = PriorityQueue()
        for l in lists:
            if l:
                q.put(use_only_first(l.val, l))
        head = point = ListNode(0)
        while not q.empty():    # PriorityQueue has no len()
            use_object = q.get()
            val = use_object._first
            node = use_object._second
            point.next = ListNode(val)
            point = point.next
            node = node.next
            if node:
                q.put(use_only_first(node.val, node))
        return head.next
		
    #----------------------------------------------------
    #Approach 2: Merge with Divide And Conquer
    #----------------------------------------------------
	def mergeKListsUsingDivideAndConquer(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        mid = len(lists) // 2
        l, r = self.mergeKListsUsingDivideAndConquer(lists[:mid]), self.mergeKListsUsingDivideAndConquer(lists[mid:])
        return self.merge(l, r)
    
    def merge(self, l, r):
        dummy = p = ListNode()
        while l and r:
            if l.val < r.val:
                p.next = l
                l = l.next
            else:
                p.next = r
                r = r.next
            p = p.next
        p.next = l or r
        return dummy.next

class Test(unittest.TestCase):
    def setUp(self) -> None:
        pass

    def tearDown(self) -> None:
        pass

    def test_mergeTwoLists(self) -> None:
        listNode = ListNode()
        s = Solution()
        for lists, solution in (
            [
                [[1,4,5],[1,3,4],[2,6]],
                [1,1,2,3,4,4,5,6]
            ],
            [
                [],
                []
            ],
            [
                [[]],
                []
            ]
        ):
            self.assertEqual(
                solution,
                ListNode.linkedListToList(s.mergeKListsUsingHeap([ListNode.initList(lst) for lst in lists])),
                "Should merge K sorted linked lists and return it as a new sorted list",
            )
            self.assertEqual(
                solution,
                ListNode.linkedListToList(s.mergeKListsUsingPriorityQueue([ListNode.initList(lst) for lst in lsts])),
                "Should merge K sorted linked lists and return it as a new sorted list",
            )
            self.assertEqual(
                solution,
                ListNode.linkedListToList(s.mergeKListsUsingDivideAndConquer([ListNode.initList(lst) for lst in lists])),
                "Should merge K sorted linked lists and return it as a new sorted list",
            )

if __name__ == "__main__":
    unittest.main()

// Definition for singly-linked list.
class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

/*
 run time O(nlgk)
 space O(1)
*/
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    if (lists.isEmpty()) return null
    return lists.build()
}

private fun Array<ListNode?>.build(start: Int = 0, end: Int = lastIndex): ListNode? {
    if (start == end) {
        return get(start)
    }

    // divide:
    val middle = start + (end - start) / 2
    val left = build(start, middle)
    val right = build(middle + 1, end)

    // conquer:
    return merge(left, right)
}

private fun merge(left: ListNode?, right: ListNode?): ListNode? {
    val head = ListNode(0)
    var pointer: ListNode? = head
    var l = left;
    var r = right
    while (l != null && r != null) {
        if (l.`val` < r.`val`) {
            pointer?.next = l
            l = l.next
        } else {
            pointer?.next = r
            r = r.next
        }
        pointer = pointer?.next
    }
    if (l != null) {
        pointer?.next = l
    } else {
        pointer?.next = r
    }
    return head.next
}

⬆️ Back to Top

LC-19:Remove Nth Node From End of List

Solution Explanation:

Solution - I (One-Pointer, Two-Pass)
---------------------------------------------------
This approach is very intuitive and easy to get.
  - We just iterate in the first-pass to find the length of the linked list - len.
  - In the next pass, iterate len - n - 1 nodes from start and delete the next node (which would be nth node from end).
  
Solution (Two-Pointer, One-Pass)
---------------------------------------------------
We are required to remove the nth node from the end of list.
For this, we need to traverse N - n nodes from the start of the list,
where N is the length of linked list.
We can do this in one-pass as follows:

  - Let's assign two pointers - fast and slow to head.
    We will first iterate for n nodes from start using the fast pointer.

  - Now, between the fast and slow pointers, there is a gap of n nodes.
    Now, just Iterate and increment both the pointers till fast reaches the last node.
	The gap between fast and slow is still of n nodes, meaning that slow is nth node from the last node (which currently is fast).

For eg. let the list be 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9, and n = 4.

1. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
   ^slow               ^fast
   |<--gap of n nodes-->|
 
 => Now traverse till fast reaches end
 
 2. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
                        ^slow               ^fast
                        |<--gap of n nodes-->|
						
'slow' is at (n+1)th node from end.
So just delete nth node from end by assigning slow -> next as slow -> next -> next (which would remove nth node from end of list).

  - Since we have to delete the nth node from end of list (And not nth from the last of list!),
    we just delete the next node to slow pointer and return the head.

Complexity Analysis:

Solution - I (One-Pointer, Two-Pass)
---------------------------------------------------
Time Complexity : O(N), where, N is the number of nodes in the given list.
Space Complexity : O(1), since only constant space is used.

Solution (Two-Pointer, One-Pass)
---------------------------------------------------
Time Complexity : O(N), where, N is the number of nodes in the given list. Although, the time complexity is same as above solution, we have reduced the constant factor in it to half.
Space Complexity : O(1), since only constant space is used.

Note : The Problem only asks us to remove the node from the linked list and not delete it.
A good question to ask in an interview for this problem would be whether we just need to remove the node from linked list or completely delete it from the memory.
Since it has not been stated in this problem if the node is required somewhere else later on, its better to just remove the node from linked list as asked.

import unittest

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    @classmethod
    def initList(self, nums):
        if not nums:
            return None
        head = None
        current = None

        for n in nums:
            if not head:
                head = ListNode(n)
                current = head
            else:
                node = ListNode(n)
                current.next = node
                current = node
        return head

    @classmethod
    def linkedListToList(self, head):
        if not head:
            return []

        pointer = head
        sll_list = []
        while pointer:
            sll_list.append(pointer.val)
            pointer = pointer.next
        return sll_list

class Solution:
    def removeNthFromEndUsingOnePointerTwoPass(self, head: ListNode, n: int) -> ListNode:
	    ptr, length = head, 0
	    while ptr:
		    ptr, length = ptr.next, length + 1
	    if length == n : return head.next
	    ptr = head
	    for i in range(1, length - n):
		    ptr = ptr.next
	    ptr.next = ptr.next.next
	    return head

    def removeNthFromEndUsingTwoPointersOnePass(self, head: ListNode, n: int) -> ListNode:
	    fast = slow = head
	    for i in range(n):
		    fast = fast.next
	    if not fast: return head.next
	    while fast.next:
		    fast, slow = fast.next, slow.next
	    slow.next = slow.next.next
	    return head

class Test(unittest.TestCase):
    def setUp(self) -> None:
        pass

    def tearDown(self) -> None:
        pass

    def test_removeNthFromEnd(self) -> None:
        sol = Solution()
        for head, n, solution in (
            [
                [1, 2, 3, 4, 5], 2,
                [1, 2, 3, 5],
            ],
            [
                [1], 1,
                []
            ],
            [
                [1, 2], 1,
                [1]
            ]
        ):
            self.assertEqual(
                ListNode.linkedListToList(sol.removeNthFromEndUsingOnePointerTwoPass(ListNode.initList(head), n)),
                solution
            )
            self.assertEqual(
                ListNode.linkedListToList(sol.removeNthFromEndUsingTwoPointersOnePass(ListNode.initList(head), n)),
                solution
            )

if __name__ == "__main__":
    unittest.main()

// Definition for singly-linked list.
class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
    val dummy = ListNode(-1)
    dummy.next = head

    var p: ListNode? = dummy
    var q: ListNode? = dummy

    for (i in 0..n) q = q?.next

    while (q != null) {
        p = p?.next
        q = q?.next
    }

    p?.next = p?.next?.next

    return dummy.next        
}

⬆️ Back to Top

Matrix

#	Title	url	Time	Space	Difficulty
0073	Set Matrix Zeroes	https://leetcode.com/problems/set-matrix-zeroes/	O(m n)*	O(1)	Medium
0054	Spiral Matrix	https://leetcode.com/problems/spiral-matrix/	O(m n)*	O(1)	Medium
0048	Rotate Image	https://leetcode.com/problems/rotate-image/	O(n^2)	O(1)	Medium
0079	Word Search	https://leetcode.com/problems/word-search/	O(m n * 3^l)*	O(l)	Medium

LC-73:Set Matrix Zeroes

Solution Explanation:

Note: m = number of rows, n = number of cols

===========================================
Brute force using O(m*n) space: 
===========================================
The initial approach is to start with creating another matrix to store the result.
From doing that, you'll notice that we want a way to know when each row and col should be changed to zero.
We don't want to prematurely change the values in the matrix to zero because as we go through it, we might change a row to 0 because of the new value.

Time Complexity: O(m*n(m+n))
===========================================
Because we are not tracking the rows and columns which we have already set to 0. In the worst case, every element in original matrix would be 0.

===========================================
Approach-1
===========================================
More optimized using O(m + n) space: 
===========================================
Intuition
-------------------------------------------
If any cell of the matrix has a zero we can record its row and column number. 
All the cells of this recorded row and column can be marked zero in the next iteration.
-------------------------------------------

To do better, we want O(m + n). How do we go about that? Well, we really just need a way to track if any row or any col has a zero,
because then that means the entire row or col has to be zero. Ok, well, then we can use an array to track the zeroes for the row and zeros for the col. 
Whenever we see a zero, just set that row or col to be True.

Space: O(m + n) for the zeroes_row and zeroes_col array.

===========================================
Approach-2
===========================================
Most optimized using O(1) space: 
===========================================
Intuition
-------------------------------------------
Rather than using additional variables to keep track of rows and columns to be reset,
we use the matrix itself as the indicators.
-------------------------------------------

But, we can do even better, O(1) - initial ask of the problem.
What if instead of having a separate array to track the zeroes, we simply use the first row or col to track them 
and then go back to update the first row and col with zeroes after we're done replacing it?
The approach to get constant space is to use first row and first col of the matrix as a tracker.

At each row or col, if you see a zero, then mark the first row or first col as zero with the current row and col.
Then iterate through the array again to see where the first row and col were marked as zero and then set that row/col as 0.
After doing that, you'll need to traverse through the first row and/or first col 
if there were any zeroes there to begin with and set everything to be equal to 0 in the first row and/or first col.

Time complexity for all Solutions 1 and 2 is O(m * n).

Space: O(1) for modification in place and using the first row and first col to keep track of zeros instead of zeroes_row and zeroes_col

Complexity Analysis:

===========================================
Approach-1
===========================================
More optimized using O(m + n) space: 
===========================================
Time  : O(m * n) where M and N are the number of rows and columns respectively.
Space : O(m + n) for the zeroes_row and zeroes_col array.

===========================================
Approach-2
===========================================
Most optimized using O(1) space: 
===========================================
Time  : O(m * n) where M and N are the number of rows and columns respectively.
Space : O(1)

from typing import List
#===========================================
#Approach-1
#===========================================
#More optimized using O(m + n) space: 
#===========================================
class Solution:
    # TC : O(m * n) where M and N are the number of rows and columns respectively.
    # SC : O(m + n) for the zeroes_row and zeroes_col array.
    def setZeroes(self, matrix: List[List[int]]) -> None:
        # input validation
        if not matrix:
            return []

        m = len(matrix)
        n = len(matrix[0])

         zeroes_row = [False] * m
         zeroes_col = [False] * n
         for row in range(m):
             for col in range(n):
                 if matrix[row][col] == 0:
                     zeroes_row[row] = True
                     zeroes_col[col] = True

         for row in range(m):
             for col in range(n):
                 if zeroes_row[row] or zeroes_col[col]:
                     matrix[row][col] = 0

#===========================================
#Approach-2
#===========================================
#Most optimized using O(1) space: 
#===========================================
class Solution:
    # TC : O(m * n) where M and N are the number of rows and columns respectively.
    # SC : O(1)
    def setZeroes(self, matrix: List[List[int]]) -> None:

        m = len(matrix)
        n = len(matrix[0])
		
        first_row_has_zero = False
        first_col_has_zero = False
        
        # iterate through matrix to mark the zero row and cols
        for row in range(m):
            for col in range(n):
                if matrix[row][col] == 0:
                    if row == 0:
                        first_row_has_zero = True
                    if col == 0:
                        first_col_has_zero = True
                    matrix[row][0] = matrix[0][col] = 0
    
        # iterate through matrix to update the cell to be zero if it's in a zero row or col
        for row in range(1, m):
            for col in range(1, n):
                matrix[row][col] = 0 if matrix[0][col] == 0 or matrix[row][0] == 0 else matrix[row][col]
        
        # update the first row and col if they're zero
        if first_row_has_zero:
            for col in range(n):
                matrix[0][col] = 0
        
        if first_col_has_zero:
            for row in range(m):
                matrix[row][0] = 0

fun setZeroes(matrix: Array<IntArray>): Unit {
    val m = matrix.size; val n = matrix[0].size
    var r0 = false; var c0 = false

    for (i in 0..m - 1) {
        for (j in 0..n - 1) {
            if (matrix[i][j] == 0) {
                if (i == 0) r0 = true
                if (j == 0) c0 = true
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }

    for (i in 1..m - 1) {
        for (j in 1..n - 1) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0
            }
        }
    }

    if (r0) {
        for (i in 0..n - 1)
            matrix[0][i] = 0
    }

    if (c0) {
        for (i in 0..m - 1)
            matrix[i][0] = 0
    }        
}

String

#	Title	url	Time	Space	Difficulty	Tag	Note
0003	Longest Substring Without Repeating Characters	https://leetcode.com/problems/longest-substring-without-repeating-characters/	O(n)	O(1)	Medium
0424	Longest Repeating Character Replacement	https://leetcode.com/problems/longest-repeating-character-replacement/	O(n)	O(1)	Medium		Sliding Window
0076	Minimum Window Substring	https://leetcode.com/problems/minimum-window-substring/	O(n)	O(k)	Hard
0242	Valid Anagram	https://leetcode.com/problems/valid-anagram/	O(n)	O(1)	Easy
0049	Group Anagrams	https://leetcode.com/problems/group-anagrams/	O(n)	O(1)	Easy
0678	Valid Parenthesis String	https://leetcode.com/problems/valid-parenthesis-string/	O(n)	O(1)	Medium
0125	Valid Palindrome	https://leetcode.com/problems/valid-palindrome/	O(n)	O(1)	Easy
0005	Longest Palindromic Substring	https://leetcode.com/problems/longest-palindromic-substring/	O(n)	O(n)	Medium		`Manacher's Algorithm`
0647	Palindromic Substrings	https://leetcode.com/problems/palindromic-substrings/	O(n)	O(n)	Medium		`Manacher's Algorithm`
0271	Encode and Decode Strings	https://leetcode.com/problems/encode-and-decode-strings/	O(n)	O(1)	Medium	🔒

LC-3:Longest Substring Without Repeating Characters

Solution Explanation:

Approach: Sliding Window Algorithm.
=================================================================================================================================================================

From the input, we can gather the following information -

1. Given data structure is a string which is a linear data structure.
2. The output must be a substring - a part of the given string.
3. Naive solution is to check for each combination of characters in the string

Are you thinking what I am thinking 🤔 ? 
Yes, this is a classic example of a problem that can be solved using the legendary technique - Sliding Window Algorithm.

Following are the steps that we will follow -

1. Have two pointers which will define the starting index start and ending index end of the current window. Both will be 0 at the beginning.
2. Declare a Set that will store all the unique characters that we have encountered.
3. Declare a variable maxLength that will keep track of the length of the longest valid substring.
4. Scan the string from left to right one character at a time.
5. If the character has not encountered before i.e., not present in the Set the we will add it and increment the end index. The maxLength will be the maximum of Set.size() and existing maxLength.
6. If the character has encounter before, i.e., present in the Set, we will increment the start and we will remove the character at start index of the string.
7. Steps #5 and #6 are moving the window.
8. After the loop terminates, return maxLength.

Complexity Analysis:

a) Time  : O(N)
============================
We are scanning the string from left to right only once, hence the time complexity will be O(n).

b) Space : O(1)
============================
We are using Set as a data structure to facilitate our computation, therefore, the space complexity should also be O(n), right? Wrong!

WHY?

The problem clearly states that the string contains only English letters, digits, symbols and spaces and are covered in 256 code points.
Therefore, a string will be made up of a combination of these characters.

Since a Set can contain only unique elements, at any point the size of Set cannot be more than 256.

What does this mean? This means that the size of set is a function independent of the size of the input.
It is a constant.
Therefore, the space complexity will be O(1) (let me know in comments if you think otherwise).

def lengthOfLongestSubstring(s: str) -> int:
    # Base condition
    if s == "":
        return 0
    # Starting index of window
    start = 0
    # Ending index of window
    end = 0
    # Maximum length of substring without repeating characters
    maxLength = 0
    # Set to store unique characters
    unique_characters = set()
    # Loop for each character in the string
    while end < len(s):
        if s[end] not in unique_characters:
            unique_characters.add(s[end])
            end += 1
            maxLength = max(maxLength, len(unique_characters))
        else:
            unique_characters.remove(s[start])
            start += 1
    return maxLength

if __name__ == "__main__":
    #Input: s = "abcabcbb"
    #Output: 3
    #Explanation: The answer is "abc", with the length of 3.
    s = "abcabcbb"
    print(lengthOfLongestSubstring(s))

fun lengthOfLongestSubstring(s: String): Int {
    // Base condition
    if (s == "") {
        return 0
    }
    // Starting window index
    var start = 0
    // Ending window index
    var end = 0
    // Maximum length of substring
    var maxLength = 0
    // This set will store the unique characters
    val uniqueCharacters: MutableSet<Char> = HashSet()
    // Loop for each character in the string
    while (end < s.length) {
        if (uniqueCharacters.add(s[end])) {
            end++
            maxLength = maxLength.coerceAtLeast(uniqueCharacters.size)
        } else {
            uniqueCharacters.remove(s[start])
            start++
        }
    }
    return maxLength
}

fun main(args: Array) {
    //Input: s = "abcabcbb"
    //Output: 3
    //Explanation: The answer is "abc", with the length of 3.
    val s = "abcabcbb"
    println(lengthOfLongestSubstring(s))
}

⬆️ Back to Top

LC-424:Longest Repeating Character Replacement

Solution Explanation:

Approach: Sliding Window Algorithm.
=================================================================================================================================================================
- The idea here is to find a window that satisfies the condition -
- count of most repeatable character + no. of allowed replacements <= length of the window
- Since the no. of allowed replacements is fixed, then the window size is directly proportional to the count of the most repeating character.
- Initially the window keeps growing from the end, until all the allowed replacements are added up in the window until it reaches the max size.
- The moment the condition is not satisfied (i.e., count of most repeatable character + no. of allowed replacements > size of the window), 
  then we need to slide the window (not shrink) 
  to the right and decrement the frequency of the character that is moved out of the window.
- If the next character coming in is the most repeating character, then the window grows or else it simply slides again.

Complexity Analysis:

Time  : O(N)
Space : O(N)

import collections
def characterReplacement(s, k):        
    # Base condition
    if s == "":
        return 0
    longest_window = 0
    window_counts = collections.defaultdict(int)
    start = 0
    for end in range(len(s)):
        window_counts[s[end]] += 1
        while ( (end - start + 1) - max(window_counts.values()) ) > k:
            window_counts[s[start]] -= 1 
            start += 1
        longest_window = max(longest_window, end - start + 1)
    return longest_window

if __name__ == "__main__":
    #Input: s = "ABAB", k = 2
    #Output: 4
    s = "ABAB"
    k = 2
    print(characterReplacement(s,k))

fun characterReplacement(s: String, k: Int): Int {
    // Base condition
    if (s == "") {
        return 0
    }
    var mostFreqCharCount = 0; var start = 0; var max=0
    val map = mutableMapOf<Char, Int>()
        
    for (end in 0 until s.length){
        map.put(s[end], map.getOrDefault(s[end], 0) + 1)
        mostFreqCharCount = Math.max(map.get(s[end])!!, mostFreqCharCount)
        if ( ( (end - start + 1) - mostFreqCharCount ) > k ) {
            map.put(s[start], map.get(s[start])!! - 1)
            start++                
        }
        max = Math.max(max, end - start + 1)
    }
    return max
}

fun main(args: Array) {
    //Input: s = "ABAB", k = 2
    //Output: 4
    val s = "ABAB"
    val k = 2
    println(characterReplacement(s,k))
}

⬆️ Back to Top

LC-76:Minimum Window Substring

Solution Explanation:

Approach: Sliding Window Algorithm.
=================================================================================================================================================================
- The idea is we use a variable-length sliding window which is gradually applied across the string.
- We use two pointers: start and end to mark the sliding window.
- We start by fixing the start pointer and moving the end pointer to the right.
- The way we determine the current window is a valid one is by checking if all the target letters have been found in the current window.
- If we are in a valid sliding window, we first make note of the sliding window of the most minimum length we have seen so far.
- Next we try to contract the sliding window by moving the start pointer.
- If the sliding window continues to be valid, we note the new minimum sliding window. 
- If it becomes invalid (all letters of the target have been bypassed), 
  we break out of the inner loop and go back to moving the end pointer to the right.

Complexity Analysis:

Time  : O(N)
Space : O(N)

import collections
def minWindow(s: str, t: str) -> str:
    # Base condition
    if (s == "" || t == "" || len(s) < len(t))  return ""
    char_freq_in_target = collections.Counter(target)
    start = 0
    end = 0
    shortest = ""
    target_len = len(target)
        
    for end in range(len(s)):
        # If we see a target letter, decrease the total target letter count
        if char_freq_in_target[s[end]] > 0:
            target_len -= 1

        # Decrease the letter count for the current letter
        # If the letter is not a target letter, the count just becomes -ve
        char_freq_in_target[s[end]] -= 1

        # If all letters in the target are found:
        while target_len == 0:
            window_len = end - start + 1
            if not shortest or window_len < len(shortest):
                # Note the new minimum window
                shortest = s[start : end + 1]

            # Increase the letter count of the current letter
            char_freq_in_target[s[start]] += 1

            # If all target letters have been seen and now, a target letter is seen with count > 0
            # Increase the target length to be found. This will break out of the loop
            if char_freq_in_target[s[start]] > 0:
                target_len += 1
                    
            start+=1
                
    return shortest

if __name__ == "__main__":
    #Input: s = "ADOBECODEBANC", t = "ABC"
    #Output: "BANC"
    s = "ADOBECODEBANC"
    t = "ABC"
    print(minWindow(s,k))

fun minWindow(s: String, t: String): String {
    // Base condition
    if (s.isEmpty() || t.isEmpty() || s.length < t.length)  return ""
    //val charFreqInTarget = IntArray(128){ 0 }
    //for(ch in t){
    //    ++charFreqInTarget[ch.toInt()]
    //}
    val charFreqInTarget = t.groupingBy { it }.eachCount().toMutableMap()        
    var start = 0
    var end = 0
    var shortest = ""
    var lengthOfTarget = t.length

    for (end in 0..s.length - 1) {
        //if (charFreqInTarget[s[end].toInt()]-- > 0) --lengthOfTarget
        if (charFreqInTarget.contains(s[end].toInt())) --lengthOfTarget
            
        while (lengthOfTarget == 0){
            if (shortest.isEmpty() || end - start + 1 < shortest.length){
                shortest = s.substring(start, end + 1)
            }
                
            //if (++charFreqInTarget[s[start].toInt()] > 0) ++lengthOfTarget
            if (charFreqInTarget.contains(s[start].toInt())) ++lengthOfTarget
            ++start
        }
    }
        
    return shortest
}

fun main(args: Array) {
    //Input: s = "anagram", t = "nagaram"
    //Output: true
    val s = "ADOBECODEBANC"
    val t = "ABC"
    println(minWindow(s,k))
}

⬆️ Back to Top

LC-678:Valid Parenthesis String

Solution Explanation:

Approach: Stack
=================================================================================================================================================================
Algorithm
----------
- We can use a stack to keep track of the order of brackets seen in s and know whether the current bracket matches the last one seen.
- The stack will only contain openBrackets and we will use the openToCloseBracket mapping to check that the latest open bracket has a matching close bracket.
- I.e. The top of the stack (stack[-1]) should be an open bracket that matches the current close bracket, if the current bracket is a close bracket.

Complexity Analysis:

Time  : O(N)
Space : O(N)

O(n) time, 
O(n) space for when each of the characters are "(", "{", "[". This would result in a stack of size n

def isValid(s: str) -> bool:
    stack = []
    openBrackets = {'(', '[', '{'}
    openToCloseBracket = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
        
    for bracket in s:
        # Only add open brackets to the stack.
        if bracket in openBrackets:
            stack.append(bracket)
        # The stack is non-empty, and the last open bracket seen matches the close bracket.
        elif stack and openToCloseBracket[stack[-1]] == bracket:
            # Remove the matching open bracket from the stack.
            stack.pop()
        # The rules for valid bracket matching have been violated.
        else:
            return False
                
    # All brackets must be paired up, so the stack must be empty by the end of the string.
    return len(stack) == 0

if __name__ == "__main__":
    #Input: s = "()[]{}"
    #Output: True
    s = "()[]{}"
    print(isValid(s))

import java.util.ArrayDeque

fun isValid(s: String): Boolean {
    val stack = ArrayDeque<Char>()

    s.forEach {

        when (it) {
            '(', '[', '{' -> stack.push(it)
            else -> {

                val end: Char = when (it) {
                    '}' -> '{'
                    ']' -> '['
                    ')' -> '('
                    else -> throw RuntimeException("Unknown char $it")
                }

                if (end != stack.poll()) return false
            }
        }
    }

    return stack.isEmpty()
}

fun main(args: Array<String>) {
    //Input: s = "()[]{}"
    //Output: True
    val s = "()[]{}"
    println(isValid(s))
}

⬆️ Back to Top

LC-5:Longest Palindromic Substring

Solution Explanation:

Approach: Manacher's Algorithm
=================================================================================================================================================================
There are many ways to solve this problem. Most common way is to treat each character of the string as the center and expand left and right.
Keep track of their lengths and return the string with maximum length.

So, what’s the problem 🤔? The problem is the time complexity - it will be O(n2). Not so good, right?

Let’s see what’s hurting us. We are expanding left and right treating each character as the center. 
What if we only expand only at the necessary characters instead of expanding at each character?

Can we do that 🤔? Yes, we can using the Manacher’s Algorithm. This algorithm intelligently uses characteristics 
of a palindrome to solve the problem in linear O(n) time -

1. The left side of a palindrome is a mirror image of its right side.
2. Odd length palindrome will be centered on a letter and even length palindrome will be centered in between 
the two letters (thus there will be total 2n + 1 centers).

Manacher’s Algorithm deals with the problem of finding the new center.
Below are the steps -

1. Initialize the lengths array to the number of possible centers.
2. Set the current center to the first center.
3. Loop while the current center is valid:
 (a) Expand to the left and right simultaneously until we find the largest palindrome around this center.
 (b) Fill in the appropriate entry in the longest palindrome lengths array.
 (c) Iterate through the longest palindrome lengths array backwards and 
     fill in the corresponding values to the right of the entry for the current center 
	 until an unknown value (as described above) is encountered.
 (d) set the new center to the index of this unknown value.
4. Return the longest substring.

Complexity Analysis:

Time Complexity  : O(N)
========================
Note that at each step of the algorithm we’re either incrementing our current position in the input string or filling in an entry 
in the lengths array. Since the lengths array has size linear in the size of the input array, 
the algorithm has worst-case linear O(N) running time.

Space Complexity : O(N)
========================
Since we are using the palindrome array to store the length of palindromes centered at each character,
the space complexity will also be O(N).

def get_updated_string(s):
    sb = ''
    for i in range(0, len(s)):
        sb += '#' + s[i]
    sb += '#'
    return sb

# Manacher's Algorithm
def longestPalindrome(s: str) -> str:
    # Update the string to put hash "#" at the beginning, end and in between each character
    updated_string = get_updated_string(s)
    # Length of the array that will store the window of palindromic substring
    length = 2 * len(s) + 1
    # List to store the length of each palindrome centered at each element
    p = [0] * length
    # Current center of the longest palindromic string
    c = 0
    # Right boundary of the longest palindromic string
    r = 0
    # Maximum length of the substring
    maxLength = 0
    # Position index
    position = -1
    for i in range(0, length):
        # Mirror of the current index
        mirror = 2 * c - i
        # Check if the mirror is outside the left boundary of current longest palindrome
        if i < r:
            p[i] = min(r - i, p[mirror])
        # Indices of the characters to be compared
        a = i + (1 + p[i])
        b = i - (1 + p[i])
        # Expand the window
        while a < length and b >= 0 and updated_string[a] == updated_string[b]:
            p[i] += 1
            a += 1
            b -= 1
        # If the expanded palindrome is expanding beyond the right boundary of
        # the current longest palindrome, then update c and r
        if i + p[i] > r:
            c = i
            r = i + p[i]
        if maxLength < p[i]:
            maxLength = p[i]
            position = i
    offset = p[position]
    result = ''
    for i in range(position - offset + 1, position + offset):
        if updated_string[i] != '#':
            result += updated_string[i]
    return result

if __name__ == "__main__":
    #Input: s = "babad"
    #Output: "bab"
    #Note: "aba" is also a valid answer.
    s = "babad"
    print(longestPalindrome(s))

fun getUpdatedString(s: String): String {
    val sb = StringBuilder()
    for (element in s) {
        sb.append("#").append(element)
    }
    sb.append("#")
    return sb.toString()
}

// Manacher's Algorithm
fun longestPalindrome(s: String): String {
    // Update the string to put hash "#" at the beginning, end and in between each character
    val updatedString = getUpdatedString(s)
    // Length of the array that will store the window of palindromic substring
    val length = 2 * s.length + 1
    // Array to store the length of each palindrome centered at each element
    val p = IntArray(length)
    // Current center of the longest palindromic string
    var c = 0
    // Right boundary of the longest palindromic string
    var r = 0
    // Maximum length of the substring
    var maxLength = 0
    // Position index
    var position = -1
    for (i in 0 until length) {
        // Mirror of the current index
        val mirror = 2 * c - i
        // Check if the mirror is outside the left boundary of current longest palindrome
        if (i < r) {
            p[i] = (r - i).coerceAtMost(p[mirror])
        }
        // Indices of the characters to be compared
        var a = i + (1 + p[i])
        var b = i - (1 + p[i])
        // Expand the window
        while (a < length && b >= 0 && updatedString[a] == updatedString[b]) {
            p[i]++
            a++
            b--
        }
        // If the expanded palindrome is expanding beyond the right boundary of
        // the current longest palindrome, then update c and r
        if (i + p[i] > r) {
            c = i
            r = i + p[i]
        }
        if (maxLength < p[i]) {
            maxLength = p[i]
            position = i
        }
    }
    val offset = p[position]
    val result = StringBuilder()
    for (i in position - offset + 1 until position + offset) {
        if (updatedString[i] != '#') {
            result.append(updatedString[i])
        }
    }
    return result.toString()
}

fun main(args: Array<String>) {
    //Input: s = "babad"
    //Output: "bab"
    //Note: "aba" is also a valid answer.    
    val s = "babad"
    println(longestPalindrome(s))
}

⬆️ Back to Top

LC-271:Encode and Decode Strings

Solution Explanation:

References: http://leetcode.libaoj.in/encode-and-decode-strings.html
            https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/Transfer-Encoding
			https://en.wikipedia.org/wiki/Chunked_transfer_encoding
=================================================================================================================================================================
Approach: Chunked Transfer Encoding ( Similar to encoding used in HTTP v1.1 )
=================================================================================================================================================================
Pay attention to this approach because last year Google likes to ask that sort of low-level optimisation.
Serialize and deserialize BST problem is a similar example.

This approach is based on the encoding used in HTTP v1.1 . It doesn't depend on the set of input characters, 
and hence is more versatile and effective than Approach 1 [ Approach 1: Non-ASCII Delimiter ].

Data stream is divided into chunks. Each chunk is preceded by its size in bytes.

Encoding Algorithm
====================================================

        +---+---+---+ +---+---+ 
Input	| t | b | c | | d | e |
        +---+---+---+ +---+---+ 

Encode          Each chunk is preceded 
                by its 4-bytes size

+---+---+---+---+---+---+---+---+---+---+---+---+---+ 
| 0 | 0 | 0 | 3 | t | b | c | 0 | 0 | 0 | 2 | d | e |
+---+---+---+---+---+---+---+---+---+---+---+---+---+ 
       \         /                 \          /
        \       /                   \        /
    size of next chunk               \      /
                                 size of next chunk

- Iterate over the array of chunks, i.e. strings.
  + For each chunk compute its length, and convert that length into 4-bytes string.
  + Append to encoded string :
    [] 4-bytes string with information about chunk size in bytes.
    [] Chunk itself.

- Return encoded string.

Decoding Algorithm
====================================================

        +---+---+---+ +---+---+ 
Input	| t | b | c | | d | e |
        +---+---+---+ +---+---+ 

----------------------------------------------------------------

Encode          Each chunk is preceded 
                by its 4-bytes size

+---+---+---+---+---+---+---+---+---+---+---+---+---+ 
| 0 | 0 | 0 | 3 | t | b | c | 0 | 0 | 0 | 2 | d | e |
+---+---+---+---+---+---+---+---+---+---+---+---+---+ 
       \         /                 \          /
        \       /                   \        /
    size of next chunk               \      /
                                 size of next chunk

----------------------------------------------------------------

Decode             1. Read next chunk length
                   2. Read chunk itself and add it to output


        +---+---+---+ +---+---+ 
	| t | b | c | | d | e |
        +---+---+---+ +---+---+ 

- Iterate over the encoded string with a pointer i initiated as 0. While i < n :
  + Read 4 bytes s[i: i + 4] . It's chunk size in bytes. Convert this 4-bytes string to integer length .
  + Move the pointer by 4 bytes i += 4 .
  + Append to the decoded array string s[i: i + length] .
  + Move the pointer by length bytes i += length .
- Return decoded array of strings.

Complexity Analysis:

Time Complexity  : O(N)
========================
O(N) both for encode and decode, where N is a number of strings in the input array.

Space Complexity : O(1)
========================
O(1) for encode to keep the output, since the output is one string.O(N) for decode keep the output, since the output is an array of strings.

class Codec:
    def len_to_str(self, x):
        """
        Encodes length of string to bytes string
        """
        x = len(x)
        bytes = [chr(x >> (i * 8) & 0xff) for i in range(4)]
        bytes.reverse()
        bytes_str = ''.join(bytes)
        return bytes_str
    
    def encode(self, strs):
        """Encodes a list of strings to a single string.
        :type strs: List[str]
        :rtype: str
        """
        # encode here is a workaround to fix BE CodecDriver error
        return ''.join(self.len_to_str(x) + x.encode('utf-8') for x in strs)
        
    def str_to_int(self, bytes_str):
        """
        Decodes bytes string to integer.
        """
        result = 0
        for ch in bytes_str:
            result = result * 256 + ord(ch)
        return result
    
    def decode(self, s):
        """Decodes a single string to a list of strings.
        :type s: str
        :rtype: List[str]
        """
        i, n = 0, len(s)
        output = []
        while i < n:
            length = self.str_to_int(s[i: i + 4])
            i += 4
            output.append(s[i: i + length])
            i += length
        return output

if __name__ == "__main__":
    input = "Hello World"
    print(f'Original word: {input}')
    strs = [s.strip() for s in input.split(' ')]
    codec = Codec()
    encodedInput = codec.encode(strs)
    decodedInput = codec.decode(encodedInput)
    result = ' '.join(decodedInput)
    print(f'Decoded word: {result}')

class Codec {
    // Encodes string length to bytes string
    fun intToString(s: String): String {
        val x: Int = s.length
        val bytes = CharArray(4)
        for (i in 3 downTo -1 + 1) {
            bytes[3 - i] = (x shr i * 8 and 0xff).toChar()
        }
        return String(bytes)
    }

    // Encodes a list of strings to a single string.
    fun encode(strs: List<String>): String {
        val sb = StringBuilder()
        for (s in strs) {
            sb.append(intToString(s))
            sb.append(s)
        }
        return sb.toString()
    }

    // Decodes bytes string to integer
    fun stringToInt(bytesStr: String): Int {
        var result = 0
        for (b in bytesStr.toCharArray()) result = (result shl 8) + b.code
        return result
    }

    // Decodes a single string to a list of strings.
    fun decode(s: String): List<String> {
        var i = 0
        val n = s.length
        val output = mutableListOf<String>()
        while (i < n) {
            val length = stringToInt(s.substring(i, i + 4))
            i += 4
            output.add(s.substring(i, i + length))
            i += length
        }
        return output
    }

}

fun main(args: Array<String>) {
    val input = "Hello World"
    println("Original word: [$input]")
    var strs: List<String> = input.split(",").map { it.trim() }
    val codec = Codec()
    val encodedInput = codec.encode(strs)
    val decodedInput = codec.decode(encodedInput)
    val result = decodedInput.joinToString(" ")
    println("Decoded word: [$result]")
}

⬆️ Back to Top

Tree

#	Title	url	Time	Space	Difficulty	Tag	Note
0104	Maximum Depth of Binary Tree	https://leetcode.com/problems/maximum-depth-of-binary-tree/	O(n)	O(h)	Easy
0100	Same Tree	https://leetcode.com/problems/same-tree/	O(n)	O(h)	Easy
0226	Invert Binary Tree	https://leetcode.com/problems/invert-binary-tree/	O(n)	O(h), O(w)	Easy
0124	Binary Tree Maximum Path Sum	https://leetcode.com/problems/binary-tree-maximum-path-sum/	O(n)	O(h)	Hard
0102	Binary Tree Level Order Traversal	https://leetcode.com/problems/binary-tree-level-order-traversal/	O(n)	O(n)	Easy
0297	Serialize and Deserialize Binary Tree	https://leetcode.com/problems/serialize-and-deserialize-binary-tree/	O(n)	O(h)	Hard	LintCode	DFS
0606	Construct String from Binary Tree	https://leetcode.com/problems/construct-string-from-binary-tree/	O(n)	O(h)	Easy
0572	Subtree of Another Tree	https://leetcode.com/problems/subtree-of-another-tree/	O(n)	O(n+m)	Easy
0105	Construct Binary Tree from Preorder and Inorder Traversal	https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/	O(n)	O(n)	Medium
0098	Validate Binary Search Tree	https://leetcode.com/problems/validate-binary-search-tree/	O(n)	O(1)	Medium
0230	Kth Smallest Element in a BST	https://leetcode.com/problems/kth-smallest-element-in-a-bst/	O(max(h, k))	O(min(h, k))	Medium
0235	Lowest Common Ancestor of a Binary Search Tree	https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/	O(h)	O(1)	Easy	EPI
0208	Implement Trie (Prefix Tree)	https://leetcode.com/problems/implement-trie-prefix-tree/	O(n)	O(1)	Medium		Trie
0211	Add and Search Word - Data structure design	https://leetcode.com/problems/add-and-search-word-data-structure-design/	O(min(n, h))	O(min(n, h))	Medium		Trie, DFS
0212	Word Search II	https://leetcode.com/problems/word-search-ii/	O(m n * 3^h)*	O(t)	Hard	LintCode	Trie, DFS

LC-104:Maximum Depth of Binary Tree

Solution Explanation:

1) Depth First Search: Post Order
- Empty tree i.e. root is None: Depth = 0
- maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1
- Time and Space Complexity: O(N)

2) Depth First Search: PreOrder
- Perform pre-order traversal and pass a variable to track the level
- Time and Space Complexity: O(N)

3) Depth First Search: Iterative Version
- Push the root and the level on the stack.
- Pop and push left and right kids of root. Update the max_level variable.
- Time and Space Complexity: O(N)

4) Breadth First Search: Iterative Version
- At every level, "queue" ends up being a list of all the nodes at that level.
  We increase the depth till the time "queue" is an empty list.
- Time and Space Complexity: O(N)

Complexity Analysis:

TC: O(N)
SC: O(N)

TC: Best case O(logN)
    Worst case O(N)
	
so typically between O(N) and O(logN)

SC:  Best case O(logN)
     Worst case O(N)

so typically between O(N) and O(logN)
	
In the worst case, the tree is completely unbalanced, e.g. each node has only left child node, 
the recursion call would occur N times (the height of the tree), therefore the storage to keep the call stack would be O(N).
But in the best case (the tree is completely balanced), the height of the tree would be log(N).
Therefore, the space complexity in this case would be O(log(N)).

NOTE: big-O complexity is asking for the worst case.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 1) Depth First Search: Post Order
class Solution_DFS_Post_Order(object):
    def maxDepth(self, root: TreeNode) -> int:
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

# 2) Depth First Search: PreOrder
from collections import deque
class Solution_DFS_Pre_Order(object):
    def maxDepth(self, root: TreeNode) -> int:
        """
        :type root: TreeNode
        :rtype: int
        """
        q, depth = deque(), 0
        if root:
            q.append(root)
        while len(q):
            depth += 1
            for _ in range(len(q)):
                x = q.popleft()
                if x.left:
                    q.append(x.left)
                if x.right:
                    q.append(x.right)
        return depth

# 3) Depth First Search: Iterative Version
class Solution_DFS_Iterative(object):
    def maxDepth(self, root: TreeNode) -> int:
        """
        :type root: TreeNode
        :rtype: int
        """
        st, max_level = [], 0
        if root:
            st.append((root, 1))
        while st:
            x, level = st.pop()
            max_level = max(max_level, level)
            if x.left:
                st.append((x.left, level+1))
            if x.right:
                st.append((x.right, level+1))
        return max_level
		
# 4) Breadth First Search: Iterative Version
from collections import  deque

class Solution_BFS_Iterative(object):
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        queue = deque()
        queue.append(root)
        depth = 0
        while queue:
            depth += 1
            l = len(queue)
            for i in range(l):
                cur_root = queue.popleft()
                if cur_root.left:
                    queue.append(cur_root.left)
                if cur_root.right:
                    queue.append(cur_root.right)
        return depth
		
# w/o using deque
class Solution_BFS_Iterative(object):
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        queue = [root]
        depth = 0
        while queue:
            depth += 1
            for i in range(len(queue)):
                cur_root = queue.pop(0)
                if cur_root.left:
                    queue.append(cur_root.left)
                if cur_root.right:
                    queue.append(cur_root.right)
        return depth

fun maxDepth(root: TreeNode?): Int = when(root) {
    null -> 0
    else -> 1 + maxOf(maxDepth(root.left), maxDepth(root.right))
}

⬆️ Back to Top

LC-124:Binary Tree Maximum Path Sum

Solution Explanation:

This problem requires quite a bit of quirky thinking steps. Take it slow until you fully grasp it.

Basics
==========================


Base Cases
==========================

Important Observations
==========================
  * These important observations are very important to understand Line 9 and Line 10 in the code.
      [x] For example, in the code (Line 9), we do something like max(get_max_gain(node.left), 0). The important part is: why do we take maximum value between 0 and maximum gain we can get from left branch? Why 0?
      [x] Check the two images below first.

      [x] The important thing is "We can only get any sort of gain IF our branches are not below zero. If they are below zero, why do we even bother considering them? Just pick 0 in that case. Therefore, we do 
	      max(<some gain we might get or not>, 0)..

Going down the recursion stack for one example:

  * Because of this, we do Line 12 and Line 13. It is important to understand the different between looking for the maximum path INVOLVING the current node in process and what we return for the node which starts the recursion stack. 
    Line 12 and Line 13 takes care of the former issue and Line 15 (and the image below) takes care of the latter issue.

  * Because of this fact, we have to return like Line 15. For our example, for node 1, which is the recursion call that 
    node 3 does for max(get_max_gain(node.left), 0), node 1 cannot include both node 6 and node 7 for a path to include 
	node 3. Therefore, we can only pick the max gain from left path or right path of node 1.

Complexity Analysis:

SC: O(n)
================
Space complexity is O(1) if you ignore the recursion call stack, since we use fixed amount of variables. 
Otherwise space complexity could be O(n) for a skewed tree in worst case. 


TC: O(n)
================
For time complexity, since we will be visiting all the nodes at least once it is O(n)

import math
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        max_path = -math.inf # placeholder to be updated
        def get_max_gain(node):
            nonlocal max_path # This tells that max_path is not a local variable
            if node is None:
                return 0

            gain_on_left = max(get_max_gain(node.left), 0) # Read the part important observations ( Line #9 )
            gain_on_right = max(get_max_gain(node.right), 0) # Read the part important observations ( Line #10 )

 		    current_max_path = node.val + gain_on_left + gain_on_right # Read first three images of going down the recursion stack ( Line #12 )
 		    max_path = max(max_path, current_max_path) # Read first three images of going down the recursion stack ( Line #13 )

            return node.val + max(gain_on_left, gain_on_right) # Read the last image of going down the recursion stack ( Line #15 )

    get_max_gain(root) # Starts the recursion chain
    return max_path

fun maxPathSum(root: TreeNode?): Int {
    var max = Int.MIN_VALUE
    
    fun recursion(root: TreeNode?): Int {
        if (root == null) return 0
        
        val l = recursion(root.left)
        val r = recursion(root.right)
        
        val lmax = maxOf(l + root.`val`, root.`val`)
        val rmax = maxOf(r + root.`val`, root.`val`)
        
        max = maxOf(max, maxOf(l + r + root.`val`, maxOf(lmax, rmax)))

        return maxOf(root.`val`, maxOf(lmax, rmax))
    }
    
    recursion(root)
    return max
}

⬆️ Back to Top

LC-102:Binary Tree Level Order Traversal

Solution Explanation

# ----------------------------------------------------
# Approach-1: Breadth First Search
# ----------------------------------------------------

 * Using BFS, at any instant only L1 and L1+1 nodes are in the queue.
 * When we start the while loop, we have L1 nodes in the queue.
 * for _ in range(len(q)) allows us to dequeue L1 nodes one by one and add L2 children one by one.
 * Time complexity: O(N). Space Complexity: O(N)

# ----------------------------------------------------
# Approach-2: Depth First Search
# ----------------------------------------------------

 * Use a variable to track level in the tree and use simple Pre-Order traversal
 * Add sub-lists to result as we move down the levels
 * Time Complexity: O(N)
 * Space Complexity: O(N) + O(h) for stack space

Complexity Analysis

# ----------------------------------------------------
# Approach-1: Breadth First Search
# ----------------------------------------------------

TC: O(N)
SC: O(N)

# ----------------------------------------------------
# Approach-2: Depth First Search
# ----------------------------------------------------

TC: O(N)
SC: O(N) + O(h) for stack space

# ----------------------------------------------------
# Approach-1: Breadth First Search
# ----------------------------------------------------
#TC: O(N)
#SC: O(N)

from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        q, result = deque(), []
        if root:
            q.append(root)
        while len(q):
            level = []
            for _ in range(len(q)):
                x = q.popleft()
                level.append(x.val)
                if x.left:
                    q.append(x.left)
                if x.right:
                    q.append(x.right)
            result.append(level)
        return result

# ----------------------------------------------------
# Approach-2: Depth First Search
# ----------------------------------------------------
#TC: O(N)
#SC: O(N) + O(h) for stack space

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        self.helper(root, 0, result)
        return result
    
    def helper(self, root, level, result):
        if root is None:
            return
        if len(result) <= level:
            result.append([])
        result[level].append(root.val)
        self.helper(root.left, level+1, result)
        self.helper(root.right, level+1, result)

⬆️ Back to Top

LC-297:Serialize and Deserialize Binary Tree

Solution Explanation:

# --------------------------------------
# Approach 1 ( Level Order for encoding )
#              BFS
#              DFS ( Iterative and Recursive )
# --------------------------------------
Use level-order traversal to encode ( to match LeetCode's serialization format ).

Time complexity for both serialize and deserialize are O(n), where n is the number of nodes in the binary tree.

# --------------------------------------
# Approach 2 ( Using Native Serialization )
# --------------------------------------
Efficient for large integers which can be packed into 4 bytes.

Serializes the tree in to following format:

<val><size_of_left_tree><size_of_right_tree><left_data><right_data>

So constant 12 bytes (4 + 4 + 4) followed by arbiatry sized byte sequences one each for left and right subtree.

Time complexity for both serialize and deserialize are O(n), where n is the number of nodes in the binary tree.

Complexity Analysis:

N = the number of nodes in the binary tree.

For both solutions:

TC : O(N)
SC : O(N)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# --------------------------------------
# Approach 1 ( Level Order for encoding )
#              BFS
#              DFS ( Iterative and Recursive )
# --------------------------------------
# N = the number of nodes in the binary tree.
# --------------------------------------
# TC : O(N)
# SC : O(N)
#
# BFS
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return "#"
        queue = [root]
        res = [str(root.val)]
        while queue:
            res += [str(node.val) if node else "#" for root in queue for node in (root.left,root.right)]
            queue = [node for root in queue for node in (root.left, root.right) if node]
        return ",".join(res)

    def deserialize(self, data):
        if data == "#":
            return None
        d = iter(data.split(","))
        root = TreeNode(int(next(d)))
        queue = [root]
        while queue:
            for node in queue:
                left = next(d)
                node.left = TreeNode(int(left)) if left!="#" else None
                right = next(d)
                node.right = TreeNode(int(right)) if right!="#" else None
            queue = [node for root in queue for node in (root.left, root.right) if node]
        return root

# Recursive DFS
class Codec:   
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return "#"
        s = "{},{},{}".format(root.val, self.serialize(root.left), self.serialize(root.right))
        return s

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        d = iter(data.split(','))
        def helper(d):
            root = next(d)
            if root == "#":
                return None
            root = TreeNode(root)
            root.left = helper(d)
            root.right = helper(d)
            return root
        return helper(d) 
		
# Iterative DFS
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return "#"
        s = "{},{},{}".format(root.val, self.serialize(root.left), self.serialize(root.right))
        return s

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == "#":
            return None
        
        root = TreeNode(int(d[0]))
        stack = [[root,0]]
        for i in d[1:]:
            t = TreeNode(int(i)) if i !="#" else None
            if stack:
                last, status = stack[-1]
                if status == 0:
                    last.left = t
                    stack[-1][1] += 1
                else:
                    last.right = t
                    stack.pop()
            if t:
                stack.append([t,0])
        return root

# --------------------------------------
# Approach 2 ( Using Native Serialization )
# --------------------------------------
# N = the number of nodes in the binary tree.
# --------------------------------------
# TC : O(N)
# SC : O(N)
import struct

class Codec:
    def serialize(self, root):
        if not root:
            return ''
        left = self.serialize(root.left)
        right = self.serialize(root.right)
        return struct.pack('iii{0}s{1}s'.format(len(left), len(right)),
                           root.val, len(left), len(right), left, right)

    def deserialize(self, data):
        if not data:
            return None
        val, left_size, right_size = struct.unpack('iii', data[:12])
        left_data, right_data = struct.unpack(
            '{0}s{1}s'.format(
                left_size,
                right_size,
            ), data[12:])
        root = TreeNode(val)
        root.left, root.right = self.deserialize(left_data), self.deserialize(right_data)
        return root

# --------------------------------------
# --------------------------------------
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

// Kotline BFS Solution
// TC : O(N)
// SC : O(N)
class Codec() {
	// Encodes a URL to a shortened URL.
    fun serialize(root: TreeNode?): String {
        val q = LinkedList<TreeNode?>()
        q.offer(root)
        
        val res = StringBuilder()
        var lastPos = 0
        while (!q.isEmpty()) {
            val node = q.poll()
            if (node == null) {
                res.append("null")
            } else {
                res.append(node.`val`)
                lastPos = res.length
                q.offer(node.left)
                q.offer(node.right)                
            }
            res.append(",")
        }
        return res.substring(0..lastPos - 1)
    }

    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? {
        if (data.isEmpty()) return null
        val list = data.split(",")
        val root = TreeNode(list[0].toInt())
        val q = ArrayDeque<TreeNode>()
        q.offer(root)
        
        var i = 1
        while (i < list.size && !q.isEmpty()) {
            val node = q.poll()
            if (i < list.size && list[i] != "null") {
                node.left = TreeNode(list[i].toInt())
                q.offer(node.left)
            }
            i++
            if (i < list.size && list[i] != "null") {
                node.right = TreeNode(list[i].toInt())
                q.offer(node.right)
            }
            i++           
        }
        return root
    }
}

⬆️ Back to Top

LC-606:Construct String from Binary Tree

Solution Explanation:

We do this recursively.

  * If the tree is empty, we return an empty string.
  * We record each child as '(' + (string of child) + ')'
  * If there is a right child but no left child, we still need to record '()' instead of empty string.

Complexity Analysis:

# Solution-1: Recursive Solution
O(T): O(n)
O(S): O(h)

# Solution-2: Iterative Solution
O(T): O(n)
O(S): O(n)

# Solution-1: Recursive Solution
class Solution:
    def tree2str(self, t: TreeNode) -> str:
        if not t: return ''
        rst = f"{t.val}"
        l = self.tree2str(t.left)
        r = self.tree2str(t.right)
        if not l and not r: return rst
        #as long as it has next level, append left branch no matter what it is
        rst += f"({l})"
        #append right branch if and only if right branch has solid value
        if r: rst += f"({r})"
        return rst

# Solution-2: Iterative Solution
class Solution:
    def tree2str(self, t: TreeNode) -> str:
        rst, s = '', [t] if t else []
        while s:
            node = s.pop()
            #only left child can possibly be empty, because right child is strictly checked
            if not node: rst += '('; continue
            elif node == ")": rst += ')'; continue
                
            rst += f"({node.val}"
            if not node.left and not node.right: continue
                
            #from here, it is if node.left or node.right, i prefer shallow indentation
            if node.right:
                s.append(')')
                s.append(node.right)
            #right child is strictly checked while left child has no check at all
            s.append(')')
            s.append(node.left)
        return rst[1:]

class Solution {
    fun tree2str(t: TreeNode?): String {
        return when {
            t == null -> ""
            t.left == null && t.right == null -> t.`val`.toString()
            t.left == null && t.right != null -> String.format("%d()(%s)", t.`val`, tree2str(t.right))
            t.left != null && t.right == null -> String.format("%d(%s)", t.`val`, tree2str(t.left))
            else -> String.format("%d(%s)(%s)", t.`val`, tree2str(t.left), tree2str(t.right))
        }
    }
}

LC-572:Subtree of Another Tree

Solution Explanation:

Tree s is traversed in a preorder traversal. 

When the generator reaches a node with the same value as the root of t, we start traversing t. 

Now s and t are being traversed in parallel and the nodes are being compared by equalNodes 
(this function checks if two nodes are equal by comparing their value and left and right children). 

The while loop will stop if the generator for t (tCurr) returns None, or if the generator for s returns None 
(in which case tCurr will NOT be none and the function will return False).

Complexity Analysis:

TC: O(n)
SC: O(n+m)

class Solution:
    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:
        def preorder(node):
            if node:
                yield node
                yield from preorder(node.left)
                yield from preorder(node.right)

        for n in preorder(t1):
            if n.val == t2.val:
                if all(a.val==b.val for a, b in zip(preorder(n), preorder(t2))):
                    return True
        return False
		
# More verbose solution w/o using built-ins
class Solution:
    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:
        def preOrder(root):
            if root:
                yield root
                for node in preOrder(root.left): yield node
                for node in preOrder(root.right): yield node
                    
        def equalNodes(sCurr, tCurr):
            if sCurr.val != tCurr.val or \
                sCurr.left and not tCurr.left or \
                tCurr.left and not sCurr.left or \
                tCurr.right and not sCurr.right or \
                sCurr.right and not tCurr.right or \
                sCurr.left and sCurr.left.val != tCurr.left.val or \
                sCurr.right and sCurr.right.val != tCurr.right.val:
                return False
            return True
        
        sIter, tIter = preOrder(s), preOrder(t)
        sCurr, tCurr = next(sIter,None), next(tIter,None) 
        while sCurr and tCurr:
            if equalNodes(sCurr,tCurr):
                sCurr, tCurr = next(sIter,None), next(tIter,None)
            else:
                if tCurr == t:
                    sCurr = next(sIter,None)
                else:
                    tIter = preOrder(t)
                    tCurr = next(tIter,None)
        return tCurr == None

class Solution {
    fun isSubtree(s: TreeNode?, t: TreeNode?): Boolean {
        return when {
            s == null && t == null -> true
            s == null && t != null -> false
            s != null && t == null -> false
            else -> isSameTree(s, t) || isSubtree(s?.left, t) || isSubtree(s?.right, t)
        }
    }

    private fun isSameTree(s: TreeNode?, t: TreeNode?): Boolean {
        return when {
            s == null && t == null -> true
            s == null && t != null -> false
            s != null && t == null -> false
            else -> s?.`val` == t?.`val` && isSameTree(s?.left, t?.left) && isSameTree(s?.right, t?.right)
        }
    }
}

⬆️ Back to Top

LC-105:Construct Binary Tree from Preorder and Inorder Traversal

Solution Explanation:

Idea:
==========================
For this solution, we can take advantage of the order of nodes in the preorder and inorder traversals. A preorder traversal is [node, left, right] while an inorder traversal is [left, node, right].

Idea:
==========================
For this solution, we can take advantage of the order of nodes in the preorder and inorder traversals. A preorder traversal is [node, left, right] while an inorder traversal is [left, node, right].

We know that the root node for a tree is the first element of the preorder array (P). We also know that every element to the left of the root element in the inorder array (I) is on the left subtree, and everything to the right of the root element in I is on the right subtree.

Since we know the length of the left and right subtrees by finding the root in I, and since we know the order of the left and right subtrees in P, we can use that to determine the location of the root node in P for each of the two subtrees.

With this information, we can define a recursive helper function (splitTree) that will split the tree into two and then recursively do the same for each subtree.

In order to make this work, we just need to pass left and right limits (ileft, iright) defining the subarray of the current subtree in I, as well as the index (pix) of the root node of the subtree in P.

At this point, we could iterate forward through I until we found out the location (imid) of the root node each time, but that would push this solution to a time complexity of O(N^2).

Instead, we can make a prelimanary index map (M) of the values in I, so that we can look up the value for imid in O(1) time in each recursion. This will lower the time complexity to O(N) at the cost of a space complexity of O(N).

In the example in the graphic above, where P = [8,2,7,1,9,3,6] and I = [7,2,1,8,3,9,6], the root would be 8, so we know that imid (its location in I) is 3, and since we still are using the full array, ileft = 0 and iright = I.length-1, or 6. This means that the left subtree is imid - ileft = 3 elements long ([7,2,1] to the left of 8 in I) and the right subtree is iright - imid = 3 elements long ([3,9,6] to the right of 8 in I).

We can apply those dimensions from I to figure out the ranges of those subtrees in P, as well. The left subtree will start right after the root in P (pix + 1), and the right subtree will start once the left subtree ends (pix + 1 + (imid - ileft).

At each recursion, if imid = ileft, then there are no nodes in the left subtree, so we shouldn't call a recursion for that side. The same applies to the right side if imid = iright.

Complexity Analysis:

Time Complexity: O(N) where N is the length of P and I
Space Complexity: O(N) for M

class Solution:
    def buildTree(self, P: List[int], I: List[int]) -> TreeNode:
        M = {I[i]: i for i in range(len(I))}
        return self.splitTree(P, M, 0, 0, len(P)-1)
    
    def splitTree(self, P: List[int], M: dict, pix: int, ileft: int, iright: int) -> TreeNode:
        rval = P[pix]
        root, imid = TreeNode(rval), M[rval]
        if imid > ileft:
            root.left = self.splitTree(P, M, pix+1, ileft, imid-1)
        if imid < iright:
            root.right = self.splitTree(P, M, pix+imid-ileft+1, imid+1, iright)
        return root

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    
    var ind = 0
    
    fun build(pre: IntArray, inOr: IntArray, l: Int, r: Int, map: MutableMap<Int, Int>): TreeNode? {
        if (ind >= inOr.size) return null
        val index = map[pre[ind]] as Int
        if (index == -1 || index > r || index < l) return null
        
        val root = TreeNode(pre[ind])
        ind++
        root.left = build(pre, inOr, l, index - 1, map)
        root.right = build(pre, inOr, index + 1, r, map)
        
        return root
    }
    
    fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
        val map = mutableMapOf<Int, Int>()
        for (i in 0 until inorder.size) {
            map[inorder[i]] = i
        }
        
        return build(preorder, inorder, 0, inorder.size - 1, map)
    }
}

⬆️ Back to Top

LC-98:Validate Binary Search Tree

Solution Explanation:

# InOrder Traversal using Morris Traversal Algorithm
-----------------------------------------------------
If we do an inorder traversal of the nodes and find that they are increasing,
then the tree will be a binary tree (we could prove this by showing that if the
tree is not a BST then the inorder will not be increasing)

We can do an inorder traversal of the tree in O(1) space with the Morris inorder
traversal. This implementation of an inorder traversal makes use of the empty
right pointers at the far right of subtrees to store the recursion stack.

Complexity Analysis:

TC: O(N)
SC: O(1)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def morris(self, node):
        while node:
            if not node.left:
                yield node.val
                node = node.right
            else:
                pre = node.left
                while pre.right and pre.right is not node:
                    pre = pre.right
                
                if pre.right is node:
                    yield node.val
                    node = node.right
                    pre.right = None
                else:
                    pre.right = node
                    node = node.left
					
	def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        
        values = self.morris(root)
        prev = next(values)
		# innocent until proven guilty
        result = True
        
        for value in values:
			# Make sure that the values are still increasing
            result = result and prev < value
            prev = value
        
        return result

⬆️ Back to Top

LC-230:Kth Smallest Element in a BST

Data Structure and Algorithm Learning Points:

How to traverse the tree

There are two general strategies to traverse a tree:

Depth First Search (DFS) In this strategy, we adopt the depth as the priority, so that one would start from a root and reach all the way down to certain leaf, and then back to root to reach another branch.

The DFS strategy can further be distinguished as preorder, inorder, and postorder depending on the relative order among the root node, left node and right node.
Breadth First Search (BFS)

We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before the ones with lower levels.

On the following figure the nodes are numerated in the order you visit them, please follow 1-2-3-4-5 to compare different strategies.

Python3 Learning Points

Introduced with PEP 255, generator functions are a special kind of function that return a lazy iterator. These are objects that you can loop over like a list. However, unlike lists, lazy iterators do not store their contents in memory.

Solution Explanation:

Hint: To solve the problem, one could use the property of BST : inorder traversal of BST is an array sorted in the ascending order.
-------------------------------

# --------------------------------------
# Approach 1: lazy in order traversal using an iterator with early stopping - condensed.
# --------------------------------------

It's a very straightforward approach with O(k) time complexity.
The idea is to build an inorder traversal of BST which is an array sorted in the ascending order.
Now the answer is the (k - 1)th element of this array.


# --------------------------------------
# Approach 2: morris in order traversal
# --------------------------------------


Reference: https://www.educative.io/edpresso/what-is-morris-traversal

Complexity Analysis:

# --------------------------------------
# Approach 1: lazy in order traversal using an iterator with early stopping - condensed.
# --------------------------------------

# TC: O(k)
# SC: O(1)
#

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        # lazy in order traversal using an iterator with early stopping
        def traverse(node: TreeNode):
            if not node:
                return
            yield from traverse(node.left)
            yield node.val
            yield from traverse(node.right)

        for i, val in enumerate(traverse(root)):
            if k - i == 1:
                return val

    # even more condensed
    def kthSmallest(self, root: TreeNode, k: int) -> int:  # O(k) time and O(1) space
        # lazy in order traversal using an iterator with early stopping - condensed
        def traverse(node: TreeNode):
            yield from (*traverse(node.left), node.val, *traverse(node.right)) if node else ()

        return next(val for i, val in enumerate(traverse(root), 1) if not k - i)


# --------------------------------------
# Approach 1: lazy in order traversal using an iterator with early stopping - condensed.
# --------------------------------------

# TC: O(k)
# SC: O(1)
#

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:

    def kthSmallest(self, root: TreeNode, k: int) -> int:  # O(k) time and O(1) space
        # Morris traversal
        node = root
        while node:
            if not node.left:
                k -= 1
                if k == 0:
                    return node.val
                node = node.right
            else:
                rightmost = node
                node = temp = node.left
                while temp.right:
                    temp = temp.right
                rightmost.left = None
                temp.right = rightmost

    # even more condensed
    def kthSmallest(self, root: TreeNode, k: int) -> int:  # O(k) time and O(1) space
        # Morris traversal - condensed
        node, val = root, None
        while k:
            if not node.left:
                val, node, k = node.val, node.right, k - 1
            else:
                rightmost, node, temp = node, node.left, node.left
                while temp.right:
                    temp = temp.right
                rightmost.left, temp.right = None, rightmost
        return val

⬆️ Back to Top

LC-235:Lowest Common Ancestor of a Binary Search Tree

Solution Explanation:

Solution-1: Iterate in BST
==============================
  * Let large = max(p.val, q.val), small = min(p.val, q.val).
  * We keep iterate root in our BST:
    [x] If root.val > large then both node p and q belong to the left subtree, go to left by root = root.left.
    [x] If root.val < small then both node p and q belong to the right subtree, go to right by root = root.right.
    [x] Now, small < root.val < large (all node.val are unique), the current root is the LCA between q and p.

Complexity Analysis:

Complexity:
==============================
Time: O(H), where H is the heigh of Binary Tree.
Space: O(1)

# Solution-1: Iterate in BST
# ==============================
# TC: O(H)
# SC: O(1)
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        small = min(p.val, q.val)
        large = max(p.val, q.val)
        while root:
            if root.val > large:  # p, q belong to the left subtree
                root = root.left
            elif root.val < small:  # p, q belong to the right subtree
                root = root.right
            else:  # Now, small <= root.val <= large -> This is the LCA between p and q
                return root
        return None

Solution Explanation:

Solution 2: Find LCA of general Binary Tree
==============================
  * There are two other solutions, which take O(N) in Time Complexity to find the LCA between p and q in the general Binary Tree, please check out this article: 
    236. Lowest Common Ancestor of a Binary Tree => https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/1306476.


Article => 236. Lowest Common Ancestor of a Binary Tree => https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/1306476.
==============================
Solution 1: Depth First Search
==============================

  * Please note that p and q always exist in the tree.
  * When dfs from the root down to its children, if current root == p or root == q then current root is the their LCA.
  * If left subtree contains one of descendant (p or q) and right subtree contains the remaining descendant (q or p) then the root is their LCA.
  * If left subtree contains both p and q then return left as their LCA.
  * If right subtree contains both p and q then return right as their LCA.

For a clear explanation, you can check video title "Lowest Common Ancestor Binary Tree" by "Tushar Roy" on Youtube.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == None or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left != None and right != None: return root
        if left != None: return left
        return right

Complexity:
==============================

  * Time: O(N), where N is number of nodes in the Binary Tree.
  * Space: O(H), where H is the heigh of Binary Tree.

Solution 2: Find Parent and Level of nodes
==============================

  * Using dfs to find parent and level of nodes.
  * Make p and q go to the same level that is if level[p] < level[q] then jump q to parents level[q] - level[p] times else jump p.
  * Jump both p and q util they meet at thier LCA.
  * Return their LCA.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def jumpParent(u, steps):
            while steps > 0:
                u = parent[u]
                steps -= 1
            return u

        def dfs(u, p, depth):
            if u == None: return
            parent[u] = p
            level[u] = depth
            dfs(u.left, u, depth + 1)
            dfs(u.right, u, depth + 1)

        parent = dict()
        level = dict()
        dfs(root, None, 0)
        if level[p] < level[q]:  # Make node p and node q the same level
            q = jumpParent(q, level[q] - level[p])
        else:
            p = jumpParent(p, level[p] - level[q])
        while q != p:  # Jump util their LCA
            q = parent[q]
            p = parent[p]
        return q

Complexity:
==============================
Time & Space: O(N), where N is number of nodes in the Binary Tree.

⬆️ Back to Top

LC-208:Implement Trie (Prefix Tree)

Solution Explanation

If we look at the following trie example, we notice that "APPLE" and "APPLY" are inserted as word (they are prefixes as well). However, "APP" is not a word, it is only a prefix. What diffrentiates "word" and "prefix" is the "is_word" flag in TrieNode class. Therefore, we can implement both search and startsWith methods together using dfs (going deep down until word/prefix is found).

A
|
P
|
P
|
L
| \
E  Y
trie.insert("APPLE")
trie.insert("APPLY")
trie.search("APPLE") // returns true
trie.search("APP") // returns false
trie.startsWith("APP") // returns true

import collections

class TrieNode(object):
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)  # Defines an empty dictionary whose "type" of "values" is TrieNode.
        self.is_word = False # determines if word is completed (end of word)

class Trie(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        current = self.root
        for letter in word:
            current = current.children[letter]
        current.is_word = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        return self.dfs(word, node)

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        return self.dfs(prefix, node, False)
    
    def dfs(self, string, node, is_word_given=True):
		# if is_word_given is True: we are looking for word
		# if is_word_given is False: we are looking for prefix
	
		# the common part of search and startsWith
        for i, c in enumerate(string):
            if c not in node.children: return False
            node = node.children[c]

		# if we run "search", is_word determines the result
		# if we run "startsWith", we return True as long as "if c not in node.children: return False" does not happen
		 return node.is_word if is_word_given else True  

if __name__ == "__main__":
    trie = Trie()
    trie.insert("APPLE")
    trie.insert("APPLY")
    trie.search("APPLE") # returns true
    trie.search("APP") # returns false
    trie.startsWith("APP") # returns true

⬆️ Back to Top

LC-211:Add and Search Word - Data structure design

Solution Explanation:

In this problem, we need to use Trie data structure. For more details go to the problem 208. Implement Trie (Prefix Tree).

So, what we have here?

TrieNode class with two values: dictionary of children and flag, if this node is end of some word.
Now, we need to implement addWord(self, word) function: we add symbol by symbol, and go deepere and deeper in our Trie. In the end we note our node as end node.
Now, about search(self, word) function. Here we use dfs(node, i) with backtracking, because we can have symbol . in our word (here node is link to Trie node and i is index of letter in word). So we need to check all options: we go to all possible children and call dfs recursively. If we found not ., but just some letter, we check if we have this letter as children, and if we have, we go deeper. If we are out of letters, that is i == len(word), we return True if current end_node is equal to 1 and false in opposite case. Finally, we return False if we can not go deeper, but we still have letters.
Now, we just return dfs(self.root, 0).
Complexity: Easy part is space complexity, it is O(M), where M is sum of lengths of all words in our Trie. This is upper bound: in practice it will be less than M and it depends, how much words are intersected. The worst time complexity is also O(M), potentially we can visit all our Trie, if we have pattern like ...... For words without ., time complexity will be O(h), where h is height of Trie. For words with several letters and several ., we have something in the middle.

Complexity Analysis:

⬆️ Back to Top

LC-212:Word Search II

Solution Explanation:

In this problem, we need to use Trie data structure. For more details go to the problem 208. Implement Trie (Prefix Tree).

So, what we have here?

TrieNode class with two values: dictionary of children and flag, if this node is end of some word.
Now, we need to implement addWord(self, word) function: we add symbol by symbol, and go deepere and deeper in our Trie. In the end we note our node as end node.
Now, about search(self, word) function. Here we use dfs(node, i) with backtracking, because we can have symbol . in our word (here node is link to Trie node and i is index of letter in word). So we need to check all options: we go to all possible children and call dfs recursively. If we found not ., but just some letter, we check if we have this letter as children, and if we have, we go deeper. If we are out of letters, that is i == len(word), we return True if current end_node is equal to 1 and false in opposite case. Finally, we return False if we can not go deeper, but we still have letters.
Now, we just return dfs(self.root, 0).

Complexity Analysis:

Complexity: Easy part is space complexity, it is O(M), where M is sum of lengths of all words in our Trie. 
This is upper bound: in practice it will be less than M and it depends, how much words are intersected. 

The worst time complexity is also O(M), potentially we can visit all our Trie, if we have pattern like ...... 
For words without . (i.e., the period sign), time complexity will be O(h), where h is height of Trie. 
For words with several letters and several . (i.e., period signs), 
we have something in the middle.

SC: O(M)
TC: O(M)
where, M = sum of length of all words in our Trie.

# SC: O(M)
# TC: O(M)
# where, M = sum of length of all words in our Trie.
class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_node = 0
        
class WordDictionary:
    def __init__(self):
        self.root = TrieNode()      

    def addWord(self, word: str) -> None:
        root = self.root
        for symbol in word:
            root = root.children.setdefault(symbol, TrieNode())
        root.end_node = 1
        
    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word): return node.end_node
               
            if word[i] == ".":
                for child in node.children:
                    if dfs(node.children[child], i+1): return True
                    
            if word[i] in node.children:
                return dfs(node.children[word[i]], i+1)
            
            return False
    
        return dfs(self.root, 0)

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

    /** Initialize your data structure here. */
    class TrieNode() {
        val children = Array<TrieNode?>(26) { null }
        var isWord = false
    }

    val trieTree = TrieNode()

    /** Adds a word into the data structure. */
    fun addWord(word: String) {
        var p = trieTree

        for (w in word) {
            val i = w - 'a'
            if (p.children[i] == null) p.children[i] = TrieNode()
            p = p.children[i]!!
        }

        p.isWord = true
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    fun search(word: String): Boolean {
        fun dfs(p: TrieNode?, start: Int): Boolean {
            if (p == null) return false

            if (start == word.length) return p.isWord
            
            if (word[start] == '.') {
                for (i in 0..25) {
                    if (dfs(p.children[i], start + 1)) {
                        return true
                    }
                }
                return false
            } else {
                val i = word[start] - 'a'
                return dfs(p.children[i], start + 1)
            }
        }
        
        return dfs(trieTree, 0)
    }

⬆️ Back to Top

Heap/Priority Queue

#	Title	url	Time	Space	Difficulty	Tag	Note
0023	Merge k Sorted Lists Solution 2	https://leetcode.com/problems/merge-k-sorted-lists/	O(nlogk)	O(1)	Hard		Heap, Divide and Conquer
0347	Top K Frequent Elements	https://leetcode.com/problems/top-k-frequent-elements/	O(n)	O(n)	Medium		Quick Select, Heap, Bucket Sort
0295	Find Median from Data Stream	https://leetcode.com/problems/find-median-from-data-stream/	O(nlogn)	O(n)	Hard	EPI, LintCode	BST, Heap

LC-23:Merge k Sorted Lists Solution 1

Data Structure Primer -- Difference between heap and priority queue

I have seen lots of solutions confuse priority queue with heap. I find a good link and list the talk below.

Concept:

1. Heap is a kind of data structure. It is a name for a particular way of storing data that makes certain operations very efficient. We can use a tree or array to describe it.

   18
  /	\
 10	 16
/ \   / \
9  5  8  12

18, 10, 16, 9, 5, 8, 12

2.Priority queue is an abstract datatype. It is a shorthand way of describing a particular interface and behavior, and says nothing about the underlying implementation.

A heap is a very good data structure to implement a priority queue. The operations which are made efficient by the heap data structure are the operations that the priority queue interface needs.

Algorithm:
Collect numbers from all lists and sort them. Then create a brand new linked list from the sorted numbers.

Implementation (99.47%):

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        values = []
        for node in lists:
            while node:
                values.append(node.val)
                node = node.next 
        head = node = ListNode(None) #dummy head 
        for x in sorted(values):
            node.next = ListNode(x)
            node = node.next 
        return head.next

Analysis:
Time complexity O(Nklog(Nk), where k is number of lists and N is the length of each list;
Space complexity O(Nk)

Algorithm:
Loop through all k lists simultaneously and only advance the one with least value. The min node is tracked in a heap.

Implementation (104ms, 81.11%):

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        pq = [(x.val, i, x) for i, x in enumerate(lists) if x]
        heapify(pq)
        dummy = node = ListNode()
        while pq: 
            _, i, x = heappop(pq)
            node.next = node = x
            if x.next: heappush(pq, (x.next.val, i, x.next))
        return dummy.next 
Analysis:
Time complexity O(Nklogk) where there are k lists and each has N nodes
Space complexity O(Nk)

Algorithm:
Divide the k lists into groups and progressively merge adjacent pairs into a bigger list.

Implementation (104ms, 81.11%):

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        """divide & conquer"""
        if not lists: return None #edge case 
        
        def merge2Lists(l1, l2):
            head = node = ListNode(None) #dummy head 
            while l1 and l2: 
                if l1.val > l2.val: l1, l2 = l2, l1
                node.next = l1
                node = node.next
                l1 = l1.next 
            node.next = l1 if l1 else l2
            return head.next 
        
        d = 1 #step 
        while d < len(lists): 
            for i in range(0, len(lists)-d, 2*d): 
                lists[i] = merge2Lists(lists[i], lists[i+d])
            d *= 2
        return lists[0]
Analysis:
Time complexity O(Nklogk) where there are k lists and each has N nodes
Space complexity O(Nk)

⬆️ Back to Top

LC-347:Top K Frequent Elements

Solution Explanation:

=================================================================================================================================================================
Solution Approach:
=================================================================================================================================================================
Make Heap
max_heap = [(-val, key) for key, val in dic.items()]
Why -val?
Inside Python is the defined Min-heap, the method of finding Max-heap in StackOverFlow, which is more in line with my lazy style: Link,set Value directly to -Value.heapify

Find K
Just put the biggest few pops out of Heap, remember that the pop out here is, nokeyval

for i in range(k):
    res.append(heapq.heappop(max_heap)[1])
return res

Complexity Analysis:

TC: O(nlogk)
SC: O(n + k)

import heapq
from collections import Counter
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        res = []
		# Build frequency table
        dic = Counter(nums)
		# Construct max heap
        max_heap = [(-val, key) for key, val in dic.items()]
        heapq.heapify(max_heap)
		# Fetch the top K and append to the result list by doing heappop
        for i in range(k):
            res.append(heapq.heappop(max_heap)[1])
        return res

import java.util.Comparator
import java.util.HashMap
import java.util.PriorityQueue

// Kotlin minHeap

fun topKFrequent(nums: IntArray, k: Int): IntArray {
    val map = HashMap<Int, Int>()
    val pq = PriorityQueue<Int>(Comparator { a, b ->
                        map[a]!!.compareTo(map[b]!!) })

    for (n in nums)
        map[n] = (map[n] ?: 0) + 1

    for (m in map) {
        pq.offer(m.key)
        if (pq.size > k)
            pq.poll()
    }

    return pq.toIntArray()
}

// Kotlin quick select

fun topKFrequent(nums: IntArray, k: Int): IntArray {
    val freq = HashMap<Int, Int>()
    for (n in nums) freq[n] = freq.getOrDefault(n, 0) + 1
    val arr = freq.keys.toIntArray()

    fun partition(start: Int, end: Int): Int {
        var l = start; var r = end
        var pivot = start
        while (l <= r) {
            while (l <= r && freq[arr[l]]!! <= freq[arr[pivot]]!!) l++
            while (l <= r && freq[arr[r]]!! > freq[arr[pivot]]!!) r--
            if (l < r) arr[l] = arr[r].also { arr[r] = arr[l] }
        }
        arr[r] = arr[pivot].also { arr[pivot] = arr[r] }
        return r
    }

    fun quickSelect(start: Int, end: Int, k: Int) {
        if (start >= end) return
        val pi = partition(start, end)
        if (pi < k) quickSelect(pi + 1, end, k)
        else if (pi > k) quickSelect(start, pi - 1, k)
    }

    quickSelect(0, arr.size - 1, arr.size - k)
    return arr.sliceArray(arr.size - k..arr.size - 1)
}

LC-295:Find Median from Data Stream

Problem Description:

The median is the middle value in an ordered integer list. If the size of the list is even, 
there is no middle value and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Solution Explanation:

=================================================================================================================================================================
Solution Approach:
=================================================================================================================================================================
The invariant of the algorithm is two heaps, small and large, each represent half of the current list.
The length of smaller half is kept to be n / 2 at all time and the length of the larger half is either n / 2 or n / 2 + 1 depend on n's parity.

This way we only need to peek the two heaps' top number to calculate median.

Any time before we add a new number, there are two scenarios, (total n numbers, k = n / 2):

(1) length of (small, large) == (k, k)
(2) length of (small, large) == (k, k + 1)
After adding the number, total (n + 1) numbers, they will become:

(1) length of (small, large) == (k, k + 1)
(2) length of (small, large) == (k + 1, k + 1)
Here we take the first scenario for example, we know the large will gain one more item and small will remain the same size,
but we cannot just push the item into large. 
What we should do is we push the new number into small and pop the maximum item from small then push it into large
(all the pop and push here are heappop and heappush). By doing this kind of operations for the two scenarios we can keep our invariant.

Therefore to add a number, we have 3 O(log n) heap operations. Luckily the heapq provided us a function "heappushpop" 
which saves some time by combine two into one. The document says:

Push item on the heap, then pop and return the smallest item from the heap. 
The combined action runs more efficiently than heappush() followed by a separate call to heappop().

Alltogether, the add operation is O(logn), The findMedian operation is O(1).

Note that the heapq in python is a min heap, thus we need to invert the values in the smaller half to mimic a "max heap".

A further observation is that the two scenarios take turns when adding numbers, thus it is possible to combine the two into one.

Complexity Analysis:

TC: O(log(n))
SC: O(1)

from heapq import *

class MedianFinder:
    def __init__(self):
        self.small = []  # the smaller half of the list, max heap (invert min-heap)
        self.large = []  # the larger half of the list, min heap

    def addNum(self, num):
        if len(self.small) == len(self.large):
            heappush(self.large, -heappushpop(self.small, -num))
        else:
            heappush(self.small, -heappushpop(self.large, num))

    def findMedian(self):
        if len(self.small) == len(self.large):
            return float(self.large[0] - self.small[0]) / 2.0
        else:
            return float(self.large[0])

import java.util.Comparator
import java.util.PriorityQueue

class MedianFinder() {

    /** initialize your data structure here. */
    val smaller = PriorityQueue<Int>(Comparator { a, b -> b - a })
    val larger  = PriorityQueue<Int>()

    fun addNum(num: Int) {
        if (smaller.isEmpty() || num <= smaller.peek()) smaller.offer(num)
        else larger.offer(num)
        if (smaller.size > larger.size + 1) larger.offer(smaller.poll())
        else if (larger.size > smaller.size) smaller.offer(larger.poll())
    }

    fun findMedian(): Double {
        val even = (larger.size + smaller.size) % 2 == 0
        return if (even) (larger.peek() + smaller.peek()) / 2.0
               else smaller.peek().toDouble()
    }
}

⬆️ Back to Top

Binary Search

#	Title	url	Time	Space	Difficulty	Tag
0035	Search Insert Position	https://leetcode.com/problems/search-insert-position/	O(logn)	O(1)	Medium
0153	Find Minimum in Rotated Sorted Array Solution 2	https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/	O(logn)	O(1)	Medium
0033	Search in Rotated Sorted Array Solution 2	https://leetcode.com/problems/search-in-rotated-sorted-array/	O(logn)	O(1)	Medium	CTCI
1011	Capacity To Ship Packages Within D Days	https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/	O(nlogn)	O(1)	Medium

LC-35:Search Insert Position

Binary Search Primer:

Before We Begin
Have you ever wondered when to use while(lo<hi) while(lo <= hi) ?
Have you ever wondered when to use left = mid + 1 left = mid right = mid + 1 right = mid ?
Have you ever wondered why your binary search algorithm stuck in an infinity loop?
Well, at least I did all that, and if you are like me this article is for you.

*I'm not writing this article to have people "remember" the code, instead, I want use this article to introduce people a gateway of solving binary search problems.
*Some of the content are sourced from here(Chinese). Much thanks to the original author.

The Idea
Set lo and hi boundary, compute mid index
Compare target with mid , adjust lo & hi accordingly

Solution Explanation:

This is a very simple binary search. (Surprisingly, all the binary search solutions I found here are much longer than mine.)
The first solution only works when there is no duplicate. In this case, we return mid whenever nums[mid]==target. 
The second solution deals with the case where duplicates are allowed.

Note that it would exit the while loop ONLY when target is not in nums. 
When this happens, the if and else statement in the last loop will also adjust l so we simply return l at the end.

Complexity Analysis:

SC: 
TC: O(log(n))

# For input without duplicates:
def searchInsert(self, nums, target):
    l , r = 0, len(nums)-1
    while l <= r:
        mid=(l+r)//2
        if nums[mid]== target:
            return mid
        if nums[mid] < target:
            l = mid+1
        else:
            r = mid-1
    return l

# For input with duplicates, we only need a little bit modification:
def searchInsert(self, nums: List[int], target: int) -> int:
    l , r = 0, len(nums)-1
    while l <= r:
        mid=(l+r)//2
		# or,
		# mid = l+(r-l)//2
        if nums[mid] < target:
            l = mid+1
        else:
            if nums[mid]== target and nums[mid-1]!=target:
                return mid
            else:
                r = mid-1
    return l
	
# For input with duplicates (More Concise Solution)
def searchInsert(self, nums: List[int], target: int) -> int:
	l, r = 0, len(nums)-1
	while l <= r:
		mid = l+(r-l)//2
		# or,
		# mid = (l+r)//2
		if nums[mid]>=target: r=mid-1
		else: l=mid+1
	return l

⬆️ Back to Top

LC-153:Find Minimum in Rotated Sorted Array Solution 2

Solution Explanation:

Binary Search Algorithm
=================================================================================================================================================================

Algorithm

1. Find the mid element of the array.

2. If mid element > first element of array this means that we need to look for the inflection point on the right of mid.

3. If mid element < first element of array this that we need to look for the inflection point on the left of mid.

          6 > 4
     +-------------+
     |             |
    \|/            |
 +---*--+------+---*--+------+------+------+
 |   4  |   5  |   6  |   7  |   2  |   3  |
 +------+------+------+------+------+------+
   Left           Mid                 Right
                     ---------------------->

In the above example mid element 6 is greater than first element 4. Hence we continue our search for the inflection point to the right of mid.

4 . We stop our search when we find the inflection point, when either of the two conditions is satisfied:

nums[mid] > nums[mid + 1] Hence, mid+1 is the smallest.

nums[mid - 1] > nums[mid] Hence, mid is the smallest.

                          +------+
                          |      |
                         \|/     |
 +------+------+------+---*--+---*--+------+
 |   4  |   5  |   6  |   7  |   2  |   3  |
 +------+------+------+------+------+------+
                        Left    Mid   Right

In the above example. With the marked left and right pointers. 
The mid element is 2. The element just before 2 is 7 and 7>2 i.e. nums[mid - 1] > nums[mid]. 
Thus we have found the point of inflection and 2 is the smallest element.

Detailed Algorithm
-----------------------

1) set left and right bounds
2) left and right both converge to the minimum index; DO NOT use left <= right because that would loop forever
  2.1) find the middle value between the left and right bounds (their average);
       can equivalently do: mid = left + (right - left) // 2,
       if we are concerned left + right would cause overflow (which would occur
       if we are searching a massive array using a language like Java or C that has
       fixed size integer types)
  2.2) the main idea for our checks is to converge the left and right bounds on the start
       of the pivot, and never disqualify the index for a possible minimum value.
  2.3) in normal binary search, we have a target to match exactly,
       and would have a specific branch for if nums[mid] == target.
       we do not have a specific target here, so we just have simple if/else.
  2.4) if nums[mid] > nums[right]
    2.4.1) we KNOW the pivot must be to the right of the middle:
           if nums[mid] > nums[right], we KNOW that the
           pivot/minimum value must have occurred somewhere to the right
           of mid, which is why the values wrapped around and became smaller.
    2.4.2) example:  [3,4,5,6,7,8,9,1,2]
           in the first iteration, when we start with mid index = 4, right index = 9.
           if nums[mid] > nums[right], we know that at some point to the right of mid,
           the pivot must have occurred, which is why the values wrapped around
           so that nums[right] is less then nums[mid]
    2.4.3) we know that the number at mid is greater than at least
           one number to the right, so we can use mid + 1 and
           never consider mid again; we know there is at least
           one value smaller than it on the right
  2.5) if nums[mid] <= nums[right]
    2.5.1) here, nums[mid] <= nums[right]:
           we KNOW the pivot must be at mid or to the left of mid:
           if nums[mid] <= nums[right], we KNOW that the pivot was not encountered
           to the right of middle, because that means the values would wrap around
           and become smaller (which is caught in the above if statement).
           this leaves the possible pivot point to be at index <= mid.

    2.5.2) example: [8,9,1,2,3,4,5,6,7]
           in the first iteration, when we start with mid index = 4, right index = 9.
           if nums[mid] <= nums[right], we know the numbers continued increasing to
           the right of mid, so they never reached the pivot and wrapped around.
           therefore, we know the pivot must be at index <= mid.

    2.5.3) we know that nums[mid] <= nums[right].
           therefore, we know it is possible for the mid index to store a smaller
           value than at least one other index in the list (at right), so we do
           not discard it by doing right = mid - 1. it still might have the minimum value.

3) at this point, left and right converge to a single index (for minimum value) since
   our if/else forces the bounds of left/right to shrink each iteration:

4) when left bound increases, it does not disqualify a value
   that could be smaller than something else (we know nums[mid] > nums[right],
   so nums[right] wins and we ignore mid and everything to the left of mid).

5) when right bound decreases, it also does not disqualify a
   value that could be smaller than something else (we know nums[mid] <= nums[right],
   so nums[mid] wins and we keep it for now).

6) so we shrink the left/right bounds to one value,
   without ever disqualifying a possible minimum.

Complexity Analysis:

Time  : O(log(N))
========================
Same as Binary Search O(log(N))

Space : O(1)
========================

from typing import List

def findMin(nums: List[int]) -> int:
    """
    :type nums: List[int]
    :rtype: int
    """
    # set left and right bounds
    left, right = 0, len(nums)-1

    # left and right both converge to the minimum index;
    # DO NOT use left <= right because that would loop forever
    while left < right:
        # find the middle value between the left and right bounds (their average);
        # can equivalently do: mid = left + (right - left) // 2,
        # if we are concerned left + right would cause overflow (which would occur
        # if we are searching a massive array using a language like Java or C that has
        # fixed size integer types)
        #mid = (left + right) // 2
        mid = left + (right - left) // 2
            
        # the main idea for our checks is to converge the left and right bounds on the left
        # of the pivot, and never disqualify the index for a possible minimum value.

        # in normal binary search, we have a target to match exactly,
        # and would have a specific branch for if nums[mid] == target.
        # we do not have a specific target here, so we just have simple if/else.
            
        if nums[mid] > nums[right]:
            # we KNOW the pivot must be to the right of the middle:
            # if nums[mid] > nums[right], we KNOW that the
            # pivot/minimum value must have occurred somewhere to the right
            # of mid, which is why the values wrapped around and became smaller.

            # example:  [3,4,5,6,7,8,9,1,2] 
            # in the first iteration, when we left with mid index = 4, right index = 9.
            # if nums[mid] > nums[right], we know that at some point to the right of mid,
            # the pivot must have occurred, which is why the values wrapped around
            # so that nums[right] is less then nums[mid]

            # we know that the number at mid is greater than at least
            # one number to the right, so we can use mid + 1 and
            # never consider mid again; we know there is at least
            # one value smaller than it on the right
            left = mid + 1
        else:
            # here, nums[mid] <= nums[right]:
            # we KNOW the pivot must be at mid or to the left of mid:
            # if nums[mid] <= nums[right], we KNOW that the pivot was not encountered
            # to the right of middle, because that means the values would wrap around
            # and become smaller (which is caught in the above if statement).
            # this leaves the possible pivot point to be at index <= mid.
                
            # example: [8,9,1,2,3,4,5,6,7]
            # in the first iteration, when we left with mid index = 4, right index = 9.
            # if nums[mid] <= nums[right], we know the numbers continued increasing to
            # the right of mid, so they never reached the pivot and wrapped around.
            # therefore, we know the pivot must be at index <= mid.

            # we know that nums[mid] <= nums[right].
            # therefore, we know it is possible for the mid index to store a smaller
            # value than at least one other index in the list (at right), so we do
            # not discard it by doing right = mid - 1. it still might have the minimum value.
            right = mid

    # at this point, left and right converge to a single index (for minimum value) since
    # our if/else forces the bounds of left/right to shrink each iteration:

    # when left bound increases, it does not disqualify a value
    # that could be smaller than something else (we know nums[mid] > nums[right],
    # so nums[right] wins and we ignore mid and everything to the left of mid).

    # when right bound decreases, it also does not disqualify a
    # value that could be smaller than something else (we know nums[mid] <= nums[right],
    # so nums[mid] wins and we keep it for now).

    # so we shrink the left/right bounds to one value,
    # without ever disqualifying a possible minimum
    return nums[left]

if __name__ == "__main__":
    #Input: nums = [3,4,5,1,2]
    #Output: 1
    #Explanation: The original array was [1,2,3,4,5] rotated 3 times.
    nums = [3,4,5,1,2]
    print(findMin(nums))

### Uncommented concise solution
from typing import List

def findMin(nums: List[int]) -> int:
    left, right = 0, len(nums)-1
    while left < right:
        mid = left + (right - left) // 2            
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    return nums[left]

if __name__ == "__main__":
    #Input: nums = [3,4,5,1,2]
    #Output: 1
    #Explanation: The original array was [1,2,3,4,5] rotated 3 times.
    nums = [3,4,5,1,2]
    print(findMin(nums))

fun findMin(nums: IntArray): Int {
    var left = 0
    var right = nums.size - 1
    while (left < right) {
        //var mid = (right + left) / 2
        var mid = left + (right - left) / 2
        if (nums[mid] >= nums[left] && nums[mid] > nums[right]) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left]
}

fun main(args: Array<String>) {
    //Input: nums = [3,4,5,1,2]
    //Output: 1
    //Explanation: The original array was [1,2,3,4,5] rotated 3 times.
    val nums = intArrayOf(3,4,5,1,2)
    println(findMin(nums))
}

⬆️ Back to Top

LC-33:Search in Rotated Sorted Array Solution 2 |

Solution Explanation:

Binary Search Algorithm
=================================================================================================================================================================
Idea:
--------------------------
We have an ascending array, which is rotated at some pivot.
Let's call the rotation the inflection point. (IP)
One characteristic the inflection point holds is: arr[IP] > arr[IP + 1] and arr[IP] > arr[IP - 1]
So if we had an array like: [7, 8, 9, 0, 1, 2, 3, 4] the inflection point, IP would be the number 9.

One thing we can see is that values until the IP are ascending. And values from IP + 1 until end are also ascending (binary search, wink, wink).
Also the values from [0, IP] are always bigger than [IP + 1, n].

Intuition:
--------------------------
We can perform a Binary Search.
If A[mid] is bigger than A[left] we know the inflection point will be to the right of us, meaning values from a[left]...a[mid] are ascending.

So if target is between that range we just cut our search space to the left.
Otherwise go right.

The other condition is that A[mid] is not bigger than A[left] meaning a[mid]...a[right] is ascending.
In the same manner we can check if target is in that range and cut the search space correspondingly.

Complexity Analysis:

Time Complexity : O(log(N))
========================
Same as Binary Search O(log(N))

Space Complexity : O(1)
========================

from typing import List

def search(nums: List[int], target: int) -> int:
    n = len(nums)
    left, right = 0, n - 1
    if n == 0: return -1
        
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target: return mid
            
        # inflection point to the right. Left is strictly increasing
        if nums[mid] >= nums[left]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
                    
        # inflection point to the left of me. Right is strictly increasing
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
            
        return -1

if __name__ == "__main__":
    #Input: nums = [4,5,6,7,0,1,2], target = 0
    #Output: 4
    nums = [4,5,6,7,0,1,2]
    target = 0
    print(search(nums, target))

fun search(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            nums[mid] == target -> return mid
            nums[left] <= nums[mid] -> if (target in nums[left] .. nums[mid]) right = mid - 1 else left = mid + 1
            nums[mid] <= nums[right] -> if (target in nums[mid] .. nums[right]) left = mid + 1 else right = mid - 1
        }
    }
    return -1
}

fun main(args: Array<String>) {
    //Input: nums = [4,5,6,7,0,1,2], target = 0
    //Output: 4
    val nums = intArrayOf(4,5,6,7,0,1,2)
    val target = 0
    println(search(nums, target))
}

⬆️ Back to Top

LC-1011:Capacity To Ship Packages Within D Days

Solution Explanation:

The intuition for this problem, stems from the fact that

a) Without considering the limiting limiting D days, if we are to solve, the answer is simply max(a)
b) If max(a) is the answer, we can still spend O(n) time and greedily find out how many partitions it will result in.

[1,2,3,4,5,6,7,8,9,10], D = 5

For this example, assuming the answer is max(a) = 10, disregarding D,
we can get the following number of days:
[1,2,3,4] [5] [6] [7] [8] [9] [10]

So by minimizing the cacpacity shipped on a day, we end up with 7 days, by greedily chosing the packages for a day limited by 10.

To get to exactly D days and minimize the max sum of any partition, we do binary search in the sum space which is bounded by [max(a), sum(a)]

Binary Search Update:
One thing to note in Binary Search for this problem, is even if we end up finding a weight, that gets us to days partitions, 
we still want to continue the space on the minimum side, because, there could be a better minimum sum that still passes <= D paritions.

In the code, this is achieved by:

if res <= D:
     hi = mid
With this check in place, when we narrow down on one element, lo == hi, we will end up with exactly the minimum sum that leads to <= D partitions.

Complexity Analysis:

TIME COMPLEXITY  : O(NlogN)
SPACE COMPLEXITY : O(1)

where, N = length of weights array

from typing import List
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        lo, hi = max(weights), sum(weights)   
        while lo < hi:
            mid = (lo + hi) // 2
            tot, res = 0, 1
            for wt in weights:
                if tot + wt > mid:
                    res += 1
                    tot = wt
                else:
                    tot += wt
            if res <= D:
                hi = mid
            else:
                lo = mid+1
        return lo

⬆️ Back to Top

Recursion

#	Title	url	Time	Space	Difficulty	Tag
0050	Pow(x, n)	https://leetcode.com/problems/powx-n/	O(1)	O(1)	Medium
0779	K-th Symbol in Grammar	https://leetcode.com/problems/k-th-symbol-in-grammar/	O(1)	O(1)	Medium
0776	Split BST	https://leetcode.com/problems/split-bst/	O(n)	O(h)	Medium	🔒

LC-50:Pow(x, n)

Solution Explanation:

Solution 1: Jump double step
============================================================
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0: return 1
        if n < 0:
            x = 1 / x
            n = -n
        step = 1
        ans = x
        while step * 2 <= n:
            ans *= ans
            step *= 2
        return ans * self.myPow(x, n - step)
		
============================================================
Complexity:
============================================================
Time: O(logN)
Space: O(1)

============================================================
Solution 2: Half pow

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0: return 1
        if n < 0: return self.myPow(1/x, -n)
        half = self.myPow(x, n//2)
        if n % 2 == 0:
            return half * half
        return half * half * x

============================================================
Complexity:
============================================================
Time: O(logN)
Space: O(1)
============================================================

Follow-up Question: Find nth root of a number
Problem statement:

Many times, we need to re-implement basic functions without using any standard library functions already implemented. For example, when designing a chip that requires very little memory space.

In this question we’ll implement a function root that calculates the n’th root of a number. The function takes a nonnegative number x and a positive integer n, and returns the positive n’th root of x within an error of 0.001 (i.e. suppose the real root is y, then the error is: |y-root(x,n)| and must satisfy |y-root(x,n)| < 0.001).

Examples:
input: x = 7, n = 3
output: 1.913

input: x = 9, n = 2
output: 3

def root(x, n):
    left = 0.0
    right = x
    epsilon = 1e-4

    def powEfficient(x, n, upBound):  # Cal x^n, up to upBound
        if n == 0: return 1
        half = powEfficient(x, n // 2, upBound)
        if half > upBound: return half
        if n % 2 == 0:
            return half * half
        return half * half * x

    while right - left > epsilon:
        mid = left + (right - left) / 2
        mul = powEfficient(mid, n, x)
        if mul <= x:  # Update answer -> Try better answer by searching in the right side
            left = mid
        else:
            right = mid
    return left

print(root(7, 3))
print(root(9, 2))

============================================================
Complexity:

Time: O(logX * logN)
Space: O(1)
============================================================

⬆️ Back to Top

LC-779:K-th Symbol in Grammar

Solution Explanation:

First one is by recursion with index and level
Second one is by rule of output and observation

Solution - 1: Implementation by recursion:
======================================================

Solution - 2: Implementation by the rule of ouput:
======================================================

Observation:

Output value is decided by the number of 1s in binary representation of (K-1)

If binary representation of K-1 has odd 1s, then output value is 1
If binary representation of K-1 has even 1s, then output value is 0

Complexity Analysis:

TC: O(N)
SC: O(1)

# Solution - 1: Implementation by recursion:
# ======================================================
class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        
        if N == 1:
            # Base case:
            return 0
        
        else:
            # General case:
            if K % 2 == 0:
                
                # even index of current level is opposite of parent level's [(K+1)//2]
                return 0 if self.kthGrammar(N-1, (K+1)//2) else 1
            else:
                # odd index of current level is the same as parent level's [(K+1)//2]
                return 1 if self.kthGrammar(N-1, (K+1)//2) else 0
				
# Solution - 2: Implementation by the rule of ouput:
# ======================================================
class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        
        return bin(K-1).count('1') % 2

⬆️ Back to Top

LC-776:Split BST

Solution Explanation:

Recursion
=============================

Intuition and Algorithm
=============================
The root node either belongs to the first half or the second half. Let's say it belongs to the first half.

Then, because the given tree is a binary search tree (BST), the entire subtree at root.left must be in the first half. However, the subtree at root.right may have nodes in either halves, so it needs to be split.

In the diagram above, the thick lines represent the main child relationships between the nodes, while the thinner colored lines represent the subtrees after the split.

Lets say our secondary answer bns = split(root.right) is the result of such a split. Recall that bns[0] and bns[1] will both be BSTs on either side of the split. The left half of bns must be in the first half, and it must be to the right of root for the first half to remain a BST. The right half of bns is the right half in the final answer.

The diagram above explains how we merge the two halves of split(root.right) with the main tree, and illustrates the line of code root.right = bns[0] in the implementations.

Complexity Analysis:

Complexity Analysis
=====================
Time Complexity: O(N), where N is the number of nodes in the input tree, as each node is checked once.

Space Complexity: O(N).

class Solution(object):
    def splitBST(self, root, V):
        if not root:
            return None, None
        elif root.val <= V:
            bns = self.splitBST(root.right, V)
            root.right = bns[0]
            return root, bns[1]
        else:
            bns = self.splitBST(root.left, V)
            root.left = bns[1]
            return bns[0], root

⬆️ Back to Top

Sliding Window

#	Title	url	Time	Space	Difficulty	Tag	Note
0003	Longest Substring Without Repeating Characters	https://leetcode.com/problems/longest-substring-without-repeating-characters/	O(n)	O(1)	Medium
0209	Minimum Size Subarray Sum	https://leetcode.com/problems/minimum-size-subarray-sum/	O(n)	O(1)	Medium		Binary Search, Sliding Window

LC-3:Longest Substring Without Repeating Characters

Solution Explanation:

Sliding window
We use a dictionary to store the character as the key, the last appear index has been seen so far as value.
seen[charactor] = index

move the pointer when you met a repeated character in your window.

indext    0    1    2    3   4   5   6   7
string    a    c    b    d   b   a   c   d
          ^                  ^
          |                  |
		left               right
		seen = {a : 0, c : 1, b : 2, d: 3} 
		# case 1: seen[b] = 2, current window  is s[0:4] , 
		#        b is inside current window, seen[b] = 2 > left = 0. Move left pointer to seen[b] + 1 = 3
		seen = {a : 0, c : 1, b : 4, d: 3} 
indext    0    1    2    3   4   5   6   7
string    a    c    b    d   b   a   c   d
						 ^   ^
					     |   |
				      left  right		
indext    0    1    2    3   4   5   6   7
string    a    c    b    d   b   a   c   d
					     ^       ^
					     |       |
				       left    right		
		# case 2: seen[a] = 0,which means a not in current window s[3:5] , since seen[a] = 0 < left = 3 
		# we can keep moving right pointer.

Complexity Analysis:

* Time complexity :O(n).
n is the length of the input string.
It will iterate n times to get the result.

* Space complexity: O(m)
m is the number of unique characters of the input.
We need a dictionary to store unique characters.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = {}
        l = 0
        output = 0
        for r in range(len(s)):
            """
            If s[r] not in seen, we can keep increasing the window size by moving right pointer
            """
            if s[r] not in seen:
                output = max(output,r-l+1)
            """
            There are two cases if s[r] in seen:
            case1: s[r] is inside the current window, we need to change the window by moving left pointer to seen[s[r]] + 1.
            case2: s[r] is not inside the current window, we can keep increase the window
            """
            else:
                if seen[s[r]] < l:
                    output = max(output,r-l+1)
                else:
                    l = seen[s[r]] + 1
            seen[s[r]] = r
        return output

⬆️ Back to Top

LC-209:Minimum Size Subarray Sum

Solution Explanation:

The result is initialized as res = n + 1.
One pass, remove the value from sum s by doing s -= A[j].
If s <= 0, it means the total sum of A[i] + ... + A[j] >= sum that we want.
Then we update the res = min(res, j - i + 1).
Finally we return the result res.

Complexity Analysis:

TC: O(N)
SC: O(1)

# TC: O(N)
# SC: O(1)
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        i, res = 0, len(nums) + 1
        for j in range(len(nums)):
            s -= nums[j]
            while s <= 0:
                res = min(res, j - i + 1)
                s += nums[i]
                i += 1
        return res % (len(nums) + 1)

⬆️ Back to Top

Greedy and Backtracking

#	Title	url	Time	Space	Difficulty
0046	Permutations	https://leetcode.com/problems/permutations/	O(n n!)*	O(n)	Medium
0078	Subsets	https://leetcode.com/problems/subsets/	O(n 2^n)*	O(1)	Medium
0039	Combination Sum	https://leetcode.com/problems/combination-sum/	O(k n^k)*	O(k)	Medium
0022	Generate Parentheses	https://leetcode.com/problems/generate-parentheses/	O(4^n / n^(3/2))	O(n)	Medium

LC-46:Permuations

Solution Explanation:

# Approach 1: Recursive with backtracking (implicit stack)
# Time: O(N*N!)
# Space: O(N!)
from typing import List
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
	    # helper
	    def recursive(nums, perm=[], res=[]):
		    if not nums: # -- NOTE [1] 
			    res.append(perm[::]) #  -- NOTE [2] 

		    for i in range(len(nums)): # [1,2,3]
			    newNums = nums[:i] + nums[i+1:]
			    perm.append(nums[i])
			    recursive(newNums, perm, res) # - recursive call will make sure I reach the leaf
			    perm.pop() # -- NOTE [3] 
		    return res
        return recursive(nums)

# Approach 2: Recursive without backtracking (implicit stack)
# Time: O(N*N!)
# Space: O(N!)
from typing import List
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums: 
            res.append(perm[::]) 

        for i in range(len(nums)): 
            newNums = nums[:i] + nums[i+1:]
            # perm.append(nums[i]) # --- instead of appending to the same variable
            newPerm = perm + [nums[i]] # --- new copy of the data/variable
            permute(newNums, newPerm, res) 
            # perm.pop()  # --- no need to backtrack
        return res
    return permute(nums)

# Approach 3 : DFS Iterative with Explicit Stack
# Time: O(E+V) which is the same as => O(N*N!)
# Space: O(N!)
from typing import List
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
	    stack = [(nums, [])]   # -- nums, path (or perms)
	    res = []
	    while stack:
		    nums, path = stack.pop()
		    if not nums:
			    res.append(path)
		    for i in range(len(nums)):   # -- NOTE [4]
			    newNums = nums[:i] + nums[i+1:]
			    stack.append((newNums, path+[nums[i]]))  # --  just like we used to do (path + [node.val]) in tree traversal
	    return res

# NOTE [4]
# The difference between itertaive tree/graph traversal we did before and this one is that
# in most tree/graph traversals we are given the DS (tree/graph/edges) whereas here we have to build the nodes before we # traverse them
# Generating the nodes is very simple, we Each node will be (nums, pathSofar)

# Approach 4 : BFS Iterative with a queue
# Time: O(E+V) which is the same as => O(N*N!)
# Space: O(N!)
from collections import deque
from typing import List
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
	    q = deque()
	    q.append((nums, []))  # -- nums, path (or perms)
	    res = []
	    while q:
		    nums, path = q.popleft()
		    if not nums:
			    res.append(path)
		    for i in range(len(nums)):
			    newNums = nums[:i] + nums[i+1:]
			    q.append((newNums, path+[nums[i]]))
	    return res

⬆️ Back to Top

LC-78:Subsets

Solution Explanation:

This is a classic backtracking problem. Every back tracking problem can be solved by using the "choose"-> "explore" -> "unchoose" strategy.
"Choosing" is based on the decision tree specific to the problem. Look at the image attached.

At every level, the decision is whether to include the first element from the remaining set into the chosen set. Based on the decision, further exploration follows.

Complexity Analysis:

Time Complexity: O(2 ^ n) :: where , n --> nums.size()
Space Complexity: O(n).

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def explore(chosen, remaining, res):
            if not remaining:
                res.append(chosen[:])
                return
            d = remaining.pop(0)
            #choose
            chosen.append(d)
            #explore
            explore(chosen, remaining, res)
            chosen.pop()
            explore(chosen, remaining, res)
            #unchoose
            remaining.insert(0, d)
        
        res = []
        chosen = []
        explore(chosen, nums, res)
        return res

⬆️ Back to Top

LC-39:Combination Sum

Solution Explanation:

# --------------------------------------
# Approach-1 : DFS (w/ Backtracking)
# --------------------------------------
Combination questions can be solved with dfs most of the time. I'm following caikehe's approach. Also, if you want to fully understand this concept and backtracking, try to finish this post and do all the examples.

We have an array [1, 2, ..., n], if k == 0, meaning combination of zero numbers which is nothing (lines #7, 8, 9), right? Return [[]].

def combine(self, n, k):
    res = [] #1
    self.dfs(range(1,n+1), k, 0, [], res) #2
    return res #3
    
def dfs(self, nums, k, index, path, res):  #4
	print('index is:', index)
    print('path is:', path)
    if k == 0:  #7
        res.append(path)  #8
        return # backtracking  #9 
    for i in range(index, len(nums)):  #10
        self.dfs(nums, k-1, i+1, path+[nums[i]], res)  #11
		
Lines #1, 2, 3 are the main function, where you initialize res = []. Also, you call the dfs function to find all the combinations, and finally, you return the res. The dfs function is the main part of the code. Lines #7, 8 were explained before. dfsfuction goes into deeper levels until these two lines get activated. Keep reading.

Let's do an example for the rest! I define levels as the number of times dfs gets called recursively before moving on in the for loop of line #10.

---- Level 0 (input: nums, k=2, index = 0, path = [], res = []).
The idea of dfs is that it starts from first entry of nums = [1, 2, ..., n]. At first, nums[0] gets chosen in line #10, it calls the dfs again in line #11 with updated inputs and goes basically one level deeper to choose the second number in the combination (note that his combination would look something like [1, ...], right? nums doesn't change, but since we have already chosen one entry, variables get updated k = k - 1. Also, since we're already chosen entry 0, index variable becomes i = i +1 to go one step deeper.

---- Level 1 (input: nums, k=1, index = 1, path = [1], res = []).
Now, in line #10, the range changes. It starts from 1 to len(nums). It goes in and calls dfs one more time.

--- Level 2 (input: nums, k=0, index = 2, path = [1,2]], res = []).
This time it gets stuck in line #7, and appends path to res. Now, res = [[1,2]].

Does this make sense?

All these level just return one combination, right? ( res = [[1,2]]). Remember going into deeper levels happened when we were in line #10 and called dfs for the first time in line #11, and then for the second time in level 1, and we ended up in level 2 and got stuck in line #7. Now, we go back one step to level 1 and move on in line #10. This time, i = 1 and index = 2. Again we go back to level 2 and return path = [1,3]. This will be appended to res to get to res = [[1,2],[1,3]]. Finally, we exhaust all indices in level 1. We end up with res = [[1,2],[1,3],

sm2774us / curated_list_of_75_leetcode_questions Goto Github PK

curated_list_of_75_leetcode_questions's Introduction

LeetCode Curated List of 75 Problems.

Algorithms

Math

Solution Explanation

Complexity Analysis

Solution Explanation

Complexity Analysis

The Math Behind the Solution

Solution Explanation

Complexity Analysis

Approach-1 ( Prefer this solution in an interview setting ).

Approach-2 ( Uses Python built-ins math.gcd, itertools.combinations and collections.Counter.most_common and data structures collections.defaultdict and collections.Counter ).

The Math Behind the Solution

Solution Explanation

Complexity Analysis

Approach-1 ( Euler's theorem ).

The Math Behind the Solution

References

Solution Explanation

Complexity Analysis

Approach-2 ( Modular Exponentiation ).

Solution Explanation

Complexity Analysis

Approach-1 ( Using Binet's Formula or the Golden Ratio ).

The Math Behind the Solution

Complexity Analysis

Approach-2 ( Using Tail Recursion ).

Complexity Analysis

Approach-3 ( Using Matrix Exponentiation - DP ).

Solution Explanation

Complexity Analysis

Approach-1 ( Sieve of Eratosthenes ).

Solution Explanation

Complexity Analysis

Approach-2 ( Recursion ).

Solution Explanation

Complexity Analysis

Array

Solution Explanation

Complexity Analysis:

Solution Explanation

Complexity Analysis:

Solution Explanation ( 2 possible solutions w/ their trade-offs explained ):

Solution Explanation

Complexity Analysis:

Solution Explanation ( 2 possible solutions w/ their trade-offs explained ):

Approach-1 ( Kadane's Algorithm ):

Approach-2 ( Divide and Conquer Algorithm ):

Solution Explanation

Complexity Analysis:

Solution Explanation:

Complexity Analysis:

Solution Explanation:

Complexity Analysis:

Solution Explanation:

Complexity Analysis:

Formal Proof than an O(N) solution exists:

Solution Explanation:

Complexity Analysis:

Bit Manipulation

Solution Explanation:

Complexity Analysis:

Solution Explanation:

Complexity Analysis:

Prerequisite:

Solution Explanation:

Complexity Analysis:

Solution Explanation:

Complexity Analysis:

Solution Explanation:

Complexity Analysis:

Dynamic Programming

Solution Explanation:

Complexity Analysis:

Solution Explanation:

Complexity Analysis:

Solution Explanation:

Interview Tips:

Approach-2 ( Uses Python built-ins `math.gcd`, `itertools.combinations` and `collections.Counter.most_common` and data structures `collections.defaultdict` and `collections.Counter` ).