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];
    }

Algorithms {Longest Palindromic Substring}

Hi,

today we will talk about “Longest Palindromic Substring” problem. I’ve developed solution about year ago but a few days remembered it and thought about it.

So, full problem description:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Ok, good, on the face of it, we can use some simple naive algorithm with O^2 complexity and problem will be solved. Good … But how we can check borders of the longest palindromic substring ? Oh, that is very interesting :)

For example we have string aba, we can use something like level order traversing and, yes, it would be BFS is not it ??? Execution steps like that :

  •  index on a; try to left – null, try to right – not null; result is not palindrome; increase index;
  •  index on b; try to left – a, try to right a, good, next level, left and right – nulls , good, palindrome; store to max palindromic instance; increment index;
  • and so on ..

OK, it’s working on simple string. What about bb string ? …

Hm, if we start from b we can get just b as max substring but we should return bb … Interesting…

Naturally we can/should check index i and i+1 and compare result, is not it ? I think so, OK, try to write and submit code to leetcode :)

public class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 1)
            return s;
 
        String longest = s.substring(0, 1); // first char
 
        for(int i = 0; i < s.length(); i++){
            String tempSubstring = substring(i, i, s);
 
            if(longest.length() < tempSubstring.length()){
                longest = tempSubstring;
            }
 
             tempSubstring = substring(i, i+1, s);
 
            if(longest.length() < tempSubstring.length()){
                longest = tempSubstring;
            }
        }
        return longest;
    }
 
    String substring(int i, int j, String s){
        while(i >=0 && j<s.length() && s.charAt(i) ==s.charAt(j)){
            i--;
            j++;
        }
        return s.substring(i+1, j);
    }
}

I’ve tried and it’s working :)

Good and thanks !!!

Algorithm {Binary Tree Maximum Path Sum}

Hey, I’ve just solved one more problem from leetcode and going to share that solution. So, solved problem calls Binary Tree Maximum Path Sum.

Problem description:

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

OK, stop and think …. What do we have ???  The main point is binary tree. We can use perfect traversing algorithms. In our case we need to use post order traversal, is not it ? OK, good, if we got left, right and current what we should check ???
We should understand how post order is working . Tree should be like that:
       1
      / \
     2   3
    / \  / \
  null null null

We will traverse to the left, check if node is null return 0 (the max path equals to 0 ) and go to the right node, again if node is null return 0 and go up to parent. Parent is 2. We should check what is the max path left +parent or right +parent. After that check if this max path biggest that current value (because left or right can be negative). Good, after that we will have max current path in other words max path for current value. So, after that we should check what is the bigger max current path or full path (full path is left + current + right, because the path can start and end at any node) and if that value biggest that stored set it like a max path. That is all, so, words are good but better code, let’s go …

public int maxPathSum(TreeNode root) {
        Integer max[] = new Integer[1];
        maxPathSum(root, max);
        return max[0];
    }
 
    public int maxPathSum(TreeNode root, Integer[] max) {
        if (root == null) {
            return 0;
        }
        int left = maxPathSum(root.left, max);
        int right = maxPathSum(root.right, max);
        int current = root.val;
 
        // choose biggest path for return
        int maxCurrentPath = max(current, max(left+current, right+current));
 
        if (max[0] == null)
            max[0] = current;
        else {
            // choose max path
            int fullPath = left + current + right;
            max[0] = max(max[0], max(maxCurrentPath, fullPath));
        }
        return maxCurrentPath;
    }

So, that is all, if you have some questions don’t hesitate to ask me :)
Cheers !!!

Algorithm {Max Points on a Line}

Hi, Today we will try to solve next problem from leetcode. The problem is Max Points on a Line.

Problem description:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

So, that is short desciption…. Try Stop and Think

What do we have, we have input array/list of points and should return max number of the points on one line. We can try to remember school math course and one part is Collinear.

Three or more points P1,P2 ,P3 , …, are said to be collinear if they lie on a single straight line .

Hm, this is our case :), we should find max points on the one line. Ok, Lets go to implement it.

    public int maxPoints(Point[] points) {
        if (points == null)
            return 0;
 
        if (points.length <= 1 || isOnePoint(points))
            return points.length;
        int max = 2; // 2 points are collinear
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (points[i].x == points[j].x && points[i].y == points[j].y)
                    continue;
                int pointsCount = 2;
                for (int k = 0; k < points.length; k++) {
                    if (k != i && k != j && areCollinear(points[i], points[j], points[k])) {
                        pointsCount++;
                    }
                }
                max = Math.max(max, pointsCount);
            }
        }
        return max;
    }
 
    boolean areCollinear(Point a, Point b, Point c){
        return (a.x - b.x) * (c.y-b.y) - (c.x-b.x) * (a.y-b.y) == 0; // collinearity formula (x1 - x2)/(x2 - x3) = (y1 -y2)/(y2 - y3
    }
 
    boolean isOnePoint(Point[] x) {
        int x0 = x[0].x;
        int y0 = x[0].y;
        for (int i = 1; i < x.length; i++) {
            if (x[i].x != x0 || x[i].y != y0)
                return false;
        }
        return true;
    }

So, that is easy, with one trick , is checking if all input array contains the same points.

        if (points.length <= 1 || isOnePoint(points))
            return points.length; 

Other cases are easy to understand, run 3 loops (to get 3 Points) check if the points different and if collinear (lay on the one line) increase count of the points, after that check with max value, if count > max assign max to current count and try other points.

The complexity of current implementation is O (N^3), memory O (1) :(,  but leetcode accepted that solution, so this is good, but…

Can we improve current solution? 

Generally yes, we can use some container like Map, for storing lines and count of the Points on that line and after that just choose what line contains max count of Points. My friend is solved the problem using that approach, Complexity will be O (N^2) and memory usage O (N). 

Thanks.