Algorithm {Implement Trie (Prefix Tree)}

Hi,

Today we are going to discuss about the Trie (Prefix Tree).  First of all lets read leetcode problem description :

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Hm… Is it all ??? Yes, that’s all description and if you are not faced with trie tree before, it would be a very hard to do something. OK, try to read something about a Trie tree, so, good explanation you can find on the wiki page and topcoder.

So, short explanation:

Insert:

We can and should run from the first char of the word and link it with the next until last char of the word. If some nodes (chars) are available we should run through linked nodes (chars) until find null node, in that case create a new one node and link it with a next. Short code to clarify above description:

Search:

So, that is good for insert, what about find a word and/or a prefix ?

As you can see

class TrieNode has isWordEnd flag. That flag will indicate which char is the end of the word. So, We should run from the first char of the searched word and check if the node (char) is available if no, just return false, if yes, try to find next.

In word case we should check isWordEnd flag on the last char, in prefix should not.

Code sample:

OK, you can below full code of the leetcode accepted solution.

Thanks!

Algorithm {Longest Valid Parentheses}

Hi,
today we will try to solve that problem. First time I’ve faced the task I did fail, Yes, I’ve thought about the task in right way but had problems in some implementation details. Today, I’ve analysed problem on the fresh mind and found/fixed my mistakes.
So, task description:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Algorithm analysis:

Judging to the task description we can image how our algorithm will work. It looks like we started from first element and run to the end when we have open parentheses “(“ we increment something by one if closed “)” – decrement. I clearly see here is LIFO algorithm. OK, we have found data structure which will be used in our algorithm. It will be stack.

OK, now try to analyse some examples from the description.

() – easiest case. Just add open element to stack and remove when we have closed one and calculate length.

(()) – more complex but with the same solution, all will work like for first case.

()() – interesting case. We have to save linking between sequence of the open closed parentheses. It means when we calculate length do not clean up current length or start index until -1 rule is happened.

-1 Rule. This rule will work in case when we have empty stack and input closed symbol like ())). So -1 rule will be triggered on the second closed parentheses.

(() – reversed case. In this case we can run in two ways. One is the calculation of length each time when closed parentheses is happened or, run algorithm from right to left like in reverse mode.

OK, let’s implement algorithm.
First implementation is reverse case:

We run from left to right and from right to left and select longest number.

Second one is each time length calculation:

Here is we can see each time calculation of the length but we stored into stack position of open parentheses and calculate diff between prev stored position and current position of loop.

That is all, both solutions are accepted by leetcode, but the task is hard and can be faced just in very strong companies.

Cheers.

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!