My Leet Code Journey

  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