Algorithm {Binary Tree Level Order Traversal II}

Hi,

Today we will work on the tree traversal task – Binary Tree Level Order Traversal II. We can see that task is pointed as second (II) it means not simple/classic level order traversal, so, let’s read task description:

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

So, as expected task is not usual classic traversal, we should print tree from bottom to top.

Stop and think what do we have and what we should to do.

We have classic binary tree. And we should traverse this tree level by level and after that create result list from end level to first. So, during traversing we can store level by level data until last and after that read from top level by level and put to result list. What data structure has that behaviour? Yes, Stack (LIFO).

So, we have analysed problem let’s implement it:

That is all, and leetcode accepted solution :)

Thanks!

Algorithm {Linked List Cycle/II}

Hi, Today we will learn how to solve two problems from leetcode – Linked List Cycle and Linked List Cycle II. So, as you can see these problems are related but first easiest and second more complex. OK, first task description:

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

So, it’s easy if you know Robert W. Floyd algorithm also called “tortoise and the hare” algorithm. Full description you can read in wiki. I am going to provide short description before implementation. Main idea of algorithm is two pointers. First one slow or tortoise, second one is fast or hare. Slow pointer will be moved node by node, fast one node after node i.e. twice faster than slow one. So, when slow pointer run through distance x fast 2x and if there is loop fast will catch up slow, this is rule to stop loop.

OK, try to implement it:

you can see that is very easy to develop and understand. OK, let’s move to the second task:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

This task is more complex, because you should find start cycle node. But if you again read tortoise and the hare algorithm you should understand this is not so hard.

Short transcript of the wiki description:

When fast caught slow, slow is stay in the same distance to first cycle node as from start to first cycle node. So, if we start new one pointer from start (or move slow or fast to start) and run node by node we will get first cycle node. Super!

Lets implement it:

Perfect, both solutions were accepted by leetcode.

Cheers!

Algorithm {Intersection of Two Linked Lists}

Hi, Today I will describe about easy but with interesting solution problem – Intersection of Two Linked Lists. OK, let’s read problem description:

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1. Notes:

  • If the two linked lists have no intersection at all, return null.

  • The linked lists must retain their original structure after the function returns.

  • You may assume there are no cycles anywhere in the entire linked structure.

  • Your code should preferably run in O(n) time and use only O(1) memory.

So, what can we see? We have two linked lists where last part can be the same, like in the pic above. OK, try to think how to find first element of the common part. First solution can be based on two loops. Run two loops for each element of list1 check all elements of list2, yes, complexity will be bad and equals to O(nm) if n ==m , O(n^2), but we do not use additional memory. Second one can be based on recursion. Main idea run through 2 lists to the end and in back way compare each element. If elements are not equal return next one. Complexity will be O(n+m) ~ O(n), but memory usage will be O(n+m) which is not good. Code example:

Third one solution can be based on the set. Run through list1, store all elements in set and after that run through list2 check if element is present it’s intersection return it if no, return null. Complexity will be O(n+m) ~ O(n), but memory usage will be O(n+m) which is not good (can be O(n) or O(m)). Code example

OK, all solutions are not good, so, we can use some trick:

  • Counts lengths of both lists.
  • Counts difference between them.
  • Run through bigger list to different length, for align both lists
  • Run through both lists and compare elements.

Hm, perfect lest implement it:

So, leetcode accepted that solution, that is good, complexity as written in task description O(n) and memory O(1). Perfect! Thanks.

Algorithm {Word Break II}

Hi,

Today we will work on hard task Word Break II. Why this task is hard? I can say, here, during resolving this problem, you will and you should use a few techniques.

First one traversing method called DFS (or BFS), second is Dynamic programming, third is some combining and tricks :) to pass tests on leetcode.

OK, try to read task description :

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

We can see, that we have some dictionary and first idea will be about traversing through dictionary, but it will be mistake. For example you have simple input string like catsanddog and dictionary with 1 billion of words, what is the complexity will be ? Yes, O(N^2) where is N equals to 1 billion. And generally I do not think that complexity of our solution should be dependent from dictionary size!

What we can todo, try to analyse … We can run through all letters in input word and try to find all words from our dic, if found put to storage (DP) end index of word (or start index) depend to the direction of string traversing. I am storing not just indexes but word too, to speed up our solution.

OK, at the end you will have something like that:

But you will get Time Limit Exceeded exception. Generally this solution is good, but we have problems in analysing words like that :

So, how to fix that problem, you can see our algorithm run from start to end and check if the counts of words equals to input word size, it means we have used all letters from input word:

But, what will be if we run from other side, I mean we are storing in start bucket end indexes

but we can store in the end buckets start indexes and run loop from end to start, Hmm … good idea try to implement:

I’ve added new class for storing start index and word to improve speed of execution

and storing end – start indexes, it means storing in end bucket start index (and word)

so, before build result I am checking if there are some solutions, I am mean if some DFS traversing way ended in last bucket.

Trying to run on leetcode and yeah-a, it’s accepted :))!!!

It means we solved problem.

We have used combination of DP and DFS for solve that problem, but after got Time Limit exception we have changed way of DFS running and tests passed.

That is all, Thanks.

Algorithm {Min Stack}

Hi, I’ve just found that leetcode added new one task and decided solve it :). SO, new task is Min Stack.

Task description:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) — Push element x onto stack.

  • pop() — Removes the element on top of the stack.

  • top() — Get the top element.

  • getMin() — Retrieve the minimum element in the stack.

As you can see we need to implement Data Structure with some rule. Rule is method getMin should work in O(1) time complexity. OK, let’s go…

We can read here how stack should work . It’s very easy as it LIFO data structure.It means last element always will be on top of the our stack. Good but how to  find min ? Yes, we can but it will be not constant time …

First idea I had was related to additional internal stack which contains just min values. What does that mean ? Please take a look to the next code fragment :

public class MinStack {
    private Stack<Integer> internal = new Stack<Integer>();
    private Stack<Integer> min = new Stack<Integer>();
    int minVal = Integer.MAX_VALUE;
 
    public void push(int x) {
        internal.push(x);
        if (minVal > x) {
            minVal = x;
            min.push(x);
        } else {
            min.push(minVal);
        }
    }
 
    public void pop() {
        internal.pop();
        minVal = min.pop();
    }
 
    public int top() {
        return internal.peek();
    }
 
    public int getMin() {
        return minVal;
    }
}

You can see that we have two internal stacks one of them contains real data for LIFO functionality other one

private Stack<Integer> min = new Stack<Integer>();

just min values. If you deeply look to method push you will see that we are pushing input val to min stack if that val < minVal in other cases we are pushing minVal.

It means if we push

-10
11
-7
-20
8

Min stack will contain

-10
-10
-10
-20
-20

during pop method we will delete top element from both stacks and all will be good.

But … leetcode told me – memory limit …

I’ve decided that leetcode wants loop implementation :) and developed it :

class MinStack {
    private Stack<Integer> internal = new Stack<Integer>();
    int minVal = Integer.MAX_VALUE;
 
    public void push(int x) {
        internal.push(x);
        if (minVal > x) {
            minVal = x;
        }
    }
 
    public void pop() {
        Integer x = internal.pop();
        if (x == minVal) {
            minVal = findMin(internal);
        }
    }
 
    private int findMin(Stack<Integer> internal) {
        int result = Integer.MAX_VALUE;
        for (Integer x : internal) {
            if (x <= result) {
                result = x;
            }
        }
        return result;
    }
 
    public int top() {
        return internal.peek();
    }
 
    public int getMin() {
        return minVal;
    }
}

In this solution main functionality is placing in pop method. Main idea  – if we deleted element from top, check if that element minVal, if yes, try to find new one minVal. Yes, time complexity for method pop will be O(n) but for getMin O(1),and … leetcode accepted this solution :). But I did not satisfied with that solution and decided to look into leetcode solution (leetcode has new functionality after your solution is accepted you can see “real” solution). So, the general idea of leetcode’s solution is the same like first my (based on 2 stacks) but with some improvements

class MinStack {
    private Stack stack = new Stack<>();
    private Stack minStack = new Stack<>();
 
    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }
 
    public void pop() {
        if (stack.pop().equals(minStack.peek())) minStack.pop();
    }
 
    public int top() {
        return stack.peek();
    }
 
    public int getMin() {
        return minStack.peek();
    }
}

you can see we do not store all min vals but just changed min. So, my first idea was good :) just needed some improvements.

But I’ve decided  to find other solution :) and did it… So, this is crazy solution based on one stack and this solution is accepted by leetcode

public class MinStack {
    private Stack<Integer> internal = new Stack<Integer>();
    int minVal = 0;
 
    public void push(int x) {
        if (internal.empty()) {
            minVal = x;
            internal.push(minVal);
            internal.push(x);
        } else if (minVal >= x) {
            internal.push(minVal);
            internal.push(x);
            minVal = x;
        } else {
            internal.push(x);
        }
    }
 
    public void pop() {
        int x = internal.pop();
        if (x == minVal) {
            minVal = internal.pop();
        }
    }
 
    public int top() {
        return internal.peek();
    }
 
    public int getMin() {
        return minVal;
    }
}

Oh, here is some magic based on the two methods push and pop. During push we are checking if input value is less than current minVal if yes, we are pushing current minVal to stack and input value if no, just input value. In pop we are reading top value from stack if that value is min, set next value from stack to min (look to the push for more understanding).

So, how that solution is really working? Try to understand it via our example:

-10
11
-7
-20
8

we are pushing these integers but internal stack will contain next elements:

-10
-10
11
-7
-10
-20
8

What can you see here, we are storing minVal in border case. Look to that list of elements and imagine next sequence of operations:

firstly you call getMin yes, minVal will be -20, good, next pop element (during pop you will check if you are deleting min element) now we have deleted 8, good, getMin will return -20. OK, call pop second time ,we are deleting -20 which current minimum, so, we should change minVal (reading next value from top we can see that next value is -10 perfect), all next pop and get min will work correctly because we handled border situation with deleting minimum (with loop solution we re-read minVal from stack).

Yes, generally last solution like prev one based on 2 stacks but more elegant for me :)

Thanks!

Algorithm {Find Minimum in Rotated Sorted ArrayII}

Hi, In additional to prev post I’ve solved next task Find Minimum in Rotated Sorted ArrayII. The main difference between two solutions is duplication. So, task description:

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

OK, if we try to run solution from Find Minimum in Rotated Sorted Array we will get some problems and incorrect result. Now we are trying, what, yes, fix our algorithm to work with duplication.

OK, original algorithm:

public int findMin(int[] num) {
        if (num.length == 0)
            return 0;
        return findMin(num, 0, num.length - 1);
    }
 
    int findMin(int[] A, int l, int r) {
        while (l < r) {
            int m = l + (r - l) / 2;
            if (A[m] > A[r]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return A[l];
    }

We can see just two conditions middle more than right or not,

            if (A[m] > A[r]) {
                l = m + 1;
            } else {
                r = m;
            }

OK, now we should handle one more condition, and yes, you are right equal ==. Generally we have to check if A[l] (left one) equals to A[m] (middle one) and equals to A[r] (right one) if yes, increase left index, or decrease right :) and it would work. Yes, complexity will be O(N).

But what will be if we try to check recursively left and right part of array, if middle element equals to right one:

if (A[m] == A[r])

It should work and complexity should be better. OK, let’s go to implement this algorithm:

    public int findMin(int[] num) {
        if (num.length == 0)
            return 0;
        return findMin(num, 0, num.length - 1);
    }
 
    int findMin(int[] A, int l, int r) {
        while (l < r) {
            int m = l + (r - l) / 2;
            if (A[m] > A[r]) {
                l = m + 1;
            } else if (A[m] == A[r]){
                return findMin(A, l, r, m);
            }else{
                r = m;
            }
        }
        return A[l];
    }
 
    private int findMin(int[] A, int l, int r, int m) {
        int rightMin = findMin(A, m+1, r);
        int leftMin = findMin(A, l, m-1);
        if(rightMin > leftMin ){
            return leftMin;
        }else {
            return rightMin;
        }
    }

We can see one additional condition and method. What is happening ? If middle element equals to right we try to recursively run into right side:

findMin(A, m+1, r);

and into left side

findMin(A, l, m-1);

after that just check what is bigger and return result. That is very good, but what is the complexity ? Of course we will have the same O(N), but actually twice faster, because real  complexity will be O(N/2) but constants are ignoring in big O notation.

So, this is all leetcode accepted solution :)

Thanks!

Algorithm {Find Minimum in Rotated Sorted Array}

Hi,

Today we will learn something about binary search. Not about original algorithm but about some interesting modification. I am talking about Find Minimum in Rotated Sorted Array from leetcode.

So, task description:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

OK, lets go to thinking about the problem.

What do we have ?

We have sorted array with some rotation.

What does rotation mean ?

Rotation is like breaking array to two parts and concat from other side (like in example , input 0 1 2 4 5 6 7, broken to 0 1 2 and   4 5 6 7 and concat to result 4 5 6 7 0 1 2).

OK, if this is sorted array we can use binary search to find needed element, is not it?

Yes, we can but we have no input element, we have to find min in input array.

Hmm, interesting  …

When I look at the example array 4 5 6 7 0 1 2 I noticed the movement of my eyes. If I look to the start of array my eyes moved to right (I am comparing with end element and see that end is smaller than start) if to the end – to left, if to the middle it depends what element I can see, to left or to right. So, I can try implement this behavior …

OK, we have two borders: start(l) and end(r) and can start usual iterative binary search.

while (l < r) {

After that calculate middle index like in binary search

int m = l + (r - l) / 2;

After that implementation of eyes behavior. If element I am looking for bigger than right one, go to the right, no, go to the left.

if (A[m] > A[r]) {
  l = m + 1;
} else {
  r = m;
}

OK, after that just return element from l or r indexes(in my solution l, but you can try r)

return A[l];

OK, that is all, try to test our solution using example array {4 5 6 7 0 1 2}:

Step one: l==0, r==6, m ==3, A[m] ==7, A[r] ==2

7 >2, so, l =m+1==4;

Step two: l==4, r==6, m ==5, A[m] ==1, A[r] ==2

1 < 2,  so, r = 5;

Step three: l==4, r==5, m ==4, A[m] ==0, A[r] ==1

0 <1, so, r=4

Step four: l==4 and r==4 (while condition is false), break loop and get element from l or r index.

Cool, working :) You can try it on leetcode to check on more test cases.

Thanks.

Full code:

    public int findMin(int[] num) {
        if (num.length == 0)
            return 0;
        return findMin(num, 0, num.length - 1);
    }
 
    int findMin(int[] A, int l, int r) {
        while (l < r) {
            int m = l + (r - l) / 2;
            if (A[m] > A[r]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return A[l];
    }