My Leet Code Journey

  Photo by trevor pye on  Unsplash Problem Description Given the root of a binary tree, then the value v and depth d , you need to add a row of nodes with value v at the given depth d . The root node is at depth 1. The adding rule is: given a positive integer depth d , for each NOT null tree nodes N of depth d-1 , create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree. Example 1: Input: A binary tree as following: 4 / \ 2 6 / \ / 3 1 5 v = 1 d = 2 Output: 4 / \ 1 1 / \ 2 6 / \ / 3 1 5 Example 2:

  Problem Description You are given an array of  k  linked-lists  lists , each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Example: Input: lists = [[1,1,5],[1,3,4],[2,6]] Output: [1,1,1,2,3,4,5,6] Explanation: The linked-lists are: [ 1->1->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->1->2->3->4->5->6 Solution Obvious Solution The obvious (and brute force) way is to navigate ALL list items, save them into an array and then sort. The time complexity is: O(kN + kNLog(kN)) since for for total k Lists (each one with average N elements), I need to visit them all and the quick sort on final array takes kNLog(kN). The space complexity is O(kN) as all values will be saved. Best Solution (to me) Since each list is already sorted, I can definitely leverage that. To start with, let me use this example: To show it more clearer, let me put some twists (showing only the left

  Photo by Nelly Antoniadou on  Unsplash Problem Description Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list . Return the linked list sorted as well . Example 1: Input: 1->1->2->2 Output: <empty> Example 2: Input: 1->2->2->3 Output: 1->3 Solution The most fun (or puzzling) part of this problem is: when you come to a node that is different in value with its previous one, you don’t know whether it’s a duplicate one until you go to its next node. To me, there is a pattern here: during an iteration, I cannot make a decision on current element before I get to following elments. Normally I can use stack for this pattern. The key is: somehow I store elements in stack (so that I can retrieve them in a reversed or original order) for now and fetch them later basing on situations.  So assume I have an input linked list like: Step by step walk-through When I iterate the list us

  Photo by  Pablo Hermoso  on  Unsplash Problem Description Given  n  non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height =  [2,1,5,6,2,3] . The largest rectangle is shown in the shaded area, which has area =  10  unit. Example: Input: [2,1,5,6,2,3] Output: 10 Solution Obvious Solution The obvious (and brute force) way is to use 2 pointers: left and right. Let left points to index 0 ~ N-1 and then right to left and N-1. For each left and right pair, I can calculate the area[left, right] using (right-left+1) * min(heights[left], heights[left+1],heights[left+2],…,heights[right]). Its time complexity is at least be O(N²). Best Solution (to me) [Credit]  This is described by @ TravellingSalesman  in disucssion area ( https://leetcode.com/problems/largest-rectangle-in-histogram/solution/ ) and here I just try to illustrate it furt

  Photo by  Michael Dziedzic  on  Unsplash Problem Description A message containing letters from  A-Z  is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a  non-empty  string containing only digits, determine the total number of ways to decode it. The answer is guaranteed to fit in a  32-bit  integer. Example 1: Input: s = "12203" Output: 2 Explanation: It could be decoded as "ABTC" (1,2,20,3) or "LTC" (12,20,3). Example 2: Input: s = "20103" Output: 1 Explanation: It could be decoded as "TJC" (20, 10, 3). Example 3: Input: s = "2030" Output: 0 Explanation: 30 could be decoded. Solution Obvious Solution The obvious (and brute force) way is to try every possible way. The solution looks like below tree and I will calculate final valid path number as the result. For example 1, it’s like a DFS way: first I can decode “1” or “12”, and then under “