Leet Code 82. Remove Duplicates from Sorted List II — Graphically Explained Python3 Solution

-

 

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

  1. When I iterate the list using a pointer (p) and first I see “1” in the beginning. Since I don’t know whether there will be more ‘1’ along the road (yet), I will just put it in the stack.

2. Now I move p to the second node and I see another “1”. This time I actually know “1” is duplicate but in case there are more “1” following, I will just throw it into the stack as well.

3. Here p points to the third node “2”, since it’s not equal to the top item of the stack (which is “1” as shown in previous step) and this is an ascending linked list, I know a duplication list of “1” ends so I will just clear the stack. And for current node “2”, again I don’t know whether it’s duplicate so I have to push it to the stack.

4. Like #2, I add the last node to the stack and move p to its next.

5. Finally I reach the end of input linked list and since the stack contains more than 2 elements (and for sure they have duplicate values), I will discard them as well. In the end, I will return an empty list (None in Python).

Another tip: a dummy header 

In above example, there is actually nothing left in the result. Consider another example 1->2->2->3, similiarly, when I visit the second node which has a different value than stack[-1] and len(stack) == 1, it means the one in the stack is a unique one, I need to put it in final result link. A little tedious handling is: normally I need to see if this unique one is the first unique one and write separate codes to tackle yes/no situations like:

if len(stack)==1 and stack[-1].val != p.val:
  if resultHeader == None:
    resultHeader = stack.pop()
    preNode = resultHeader
  else:
    preNode.next = stack.pop()
    preNode = preNode.next
....
#finally return resultHeader
return resultHeader

It would be beautiful if I can use the same set of codes for both situations! And actually there is a way like:

resultHeader = ListNode() #this is a dummy header
preNode = resultHeader
if len(stack)==1 and stack[-1].val != p.val:
  preNode.next = stack.pop()
  preNode = preNode.next
....
#finally return resultHeader.next
return resultHeader.next

Source Code

Time & Space Complexity

All nodes will be visited once so time complexity is O(N). Stack may contain all nodes in worst case (for example, all elements are distinct) and in that case, space complexity will be O(N).

Extended Reading

Python3 cheatsheet:

https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549

Comments

Post a Comment

Popular posts from this blog

Leet Code 1060. Missing Element in Sorted Array — Explained Python3 Solution

-
Image
Problem Description Given a sorted array  A  of  unique  numbers, find the  K -th  missing number starting from the leftmost number of the array.   Example 1: Input: A = [4,7,9,10] , K = 1 Output: 5 Explanation: The first missing number is 5. Example 2: Input: A = [4,7,9,10] , K = 3 Output: 8 Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8. Solution Seeing the word " sorted " reminds me that there must be some trick to play with. One common thought of mine is binary lookup , which is used for quickly, in O(logN), to locate a specific element. And it turns out similar thoughts applies to this problem as well. Before getting to that, let me explain the brute force way a little bit. First I need to set a counter to count missing number I find as of now, in the beginning, it will be 0 for sure. Then I can certainly iterate the numbers one by one, the moment I get to index i, I will check if A[i] is the last element, if yes, then the miss
Read more

Leet Code 84. Largest Rectangle in Histogram — Graphically Explained Python3 Solution

-
Image
  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
Read more

LeetCode 23. Merge k Sorted Lists— Graphically Explained Python3 Solution

-
Image
  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
Read more