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

Algorithm {Reverse Integer}

Hi, Today I’ve choose easy task, but need to explain my thinking during dev process.

So, task :

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

OK, It’s easy, we have one number and need to get reversed version. What we have to do:

1) Convert to string and reverse string ? Yes we can, but complexity will be not good.

2)  Try to copy last number to new integer, and loop until input number would be  > than 0, yes, we can and it is easy and cool.

Second variant based on the 3 math operations  : *, / and %.

Code :

public int reverse(int x) {
    int reverse = 0;
    while(x!=0){
      reverse = reverse*10+x%10;
      x=x/10;
     }
   return reverse;
}

Explanation:

1) Run loop until input number bigger than 0 (as described below)

while(x!=0){

2) move reverse to next cell

reverse*10

3) Read from input x last cell

x%10

4) Delete last cell from input x

x=x/10;

So, This is all :) Easy, is not it ?

Thanks.

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.

Algorithm {Reverse Words in a String}

Hey, today we will try to solve “Reverse Words in a String” task for leetcode.

Task description:

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Clarification:

  • What constitutes a word?
    A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces?
    Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words?
    Reduce them to a single space in the reversed string.

Stop and think…

You can see that is easy task. I think there are a lot ways to solve this task I will provide just a one. So, what is the solution can be ?

For example:

-  we can create new one string and goes through input string from end to start  and copy all elements from input to created string, can work ? Why not …

- we can create four indexes like next

        int firstWordStart = 0;
        int firstWordEnd = 0;
        int lastWordStart = s.length()-1;
        int lastWordEnd = s.length()-1;

and work with these indexes, till

firstWordEnd < lastWordStart

but we should manage string with shifting all words because length of first and last words can be diff, So, That is hard but can be solution with swap in place.

- we can use recursion and if we found whitespace start next recursion cycle with string without first word and after recursion add first word to the end (it’s like Reverse LinkedList {Recursion implementation} ), that is good solution, but can be problem with stack memory.

- we can split words by whitespace char ” ” and reverse all words in splitted array after that create result string from array, that solution like first but more elegant for my point of view, so, I am going to implement the solution (leetcode accepted it, so, it’s right :) )

public String reverseWords(String s) {
       s = s.trim();
       String [] data = s.split(" ");
       int lastIndex = data.length-1;
       for(int i = 0; i < data.length/2; i++){
        swap(data, i, lastIndex);
        lastIndex--;
       }
       return returnString(data);
    }
 
    void swap(String[] data, int startIndex, int endIndex){
        String temp;
        temp = data[endIndex];
        data[endIndex] = data[startIndex];
        data[startIndex] = temp;
    }
 
    String returnString(String [] data){
        StringBuilder result = new StringBuilder();
        for(String datum:data){
            if(datum!=null && datum.trim().length()!=0)
                result.append(datum).append(" ");
        }
        return result.toString().trim();
    }

So, we have 3 methods, first is main and executing main logic.

Next one swap, swap is very easy, just swapping elements in array.

Last one is reversed string creator.

So, that is all…

Cheers !

 

Algorithm {Triangle}

Hey, next problem from leetcode will be Triangle. Task description:

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

 Stop and think …  

Judging to example we should go level by level and choose smallest “connected” value . Why I’ve written “connected” because if we have something like  that

   [5,6,7],
  [4,4,1,8]

we should choose 6,1 but not 5,4 because sum 6+1 < 5+4. OK interesting observation… So, what will be if we start from bottom to top ? We can choose smallest number and all will be correct. That is good, but how to check “connection”. In this situation we can use rule from Dynamic Programming(DP) (Store sum under i position of i-element from next level and min from i and i+1 element from stored values.) OK, lets go …

    public int minimumTotal(@NotNull ListList<List<Integer>> triangle) {
        if (triangle.size() == 0) return 0;
        int[] cache = new int[triangle.size()];
        List<Integer> bottom = triangle.get(triangle.size() - 1);
        for (int i = 0; i < cache.length; i++) {
            cache[i] = bottom.get(i);
        }
        int layer = cache.length - 2;
        while (layer >= 0) {
            List<Integer> list = triangle.get(layer);
            for (int i = 0; i <= layer; i++) {
                cache[i] = list.get(i) + Math.min(cache[i], cache[i + 1]);
            }
            layer--;
        }
        return cache[0];
    }

What I’ve written :

Create cache (remember about DP)

int[] cache = new int[triangle.size()];

Get last line(level) from triangle and put to cache

List<Integer> bottom = triangle.get(triangle.size() - 1);
for (int i = 0; i < cache.length; i++) {
  cache[i] = bottom.get(i);
}

after that start from next level and

Store sum under i position of i-element from next level and min from i and i+1 element from stored values.

while (layer >= 0) {
  List<Integer> list = triangle.get(layer);
  for (int i = 0; i <= layer; i++) {
   cache[i] = list.get(i) + Math.min(cache[i], cache[i + 1]);
  }
  layer--;
}

How this technique is working ? That is very easy, try to test our example :

  • firstly we have put last level to cache , so, cache contains next values
[4,1,8,3]
  • start loop from next level
[6,5,7],

i == 0, so, we store under 0-position  smallest sum  (6+4 or 6+1)

cache[i] = list.get(i) + Math.min(cache[i], cache[i + 1]);

next positions the same, OK after second line we will have our cache like next

[7,6,8,3]
  • go to next level
[3,4],

cache will be next

[9,9,8,3]
  • go to next level
[2]

cache will be next

[11,9,8,3] 

so, just return 0 position and that is all

  return cache[0];

So, we solved next task, that is good :) Thanks!

Algorithm {Single Number}

Hey, We are working on next task from leetcode. So, next task will be …. , {Single Number} :).

Task:

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Stop and think …

What we have, input array of integers and we should find one NOT DUPLICATE number. So, it’s easy … Go to the math knowledge and try to remember XOR if you don’t remember you can try to refresh knowledge in XOR Truth Table. So, main idea that two equal numbers will return 0. What does it mean ??? If we have array like next

1,1,4,4,5

And try to XOR all values we will get 5, OK, that is very good and we can start use that functionality to develop our algorithm.

Lets go :

public int singleNumber(int[] A) {
        int result = 0;
        for(int i = 0; i < A.length; i ++){
            result^=A[i];
        }
        return result;
}

OK, what we can see, we have result value, and one loop all values are XORed to the result (read about XOR functionality) so after the loop we will have Single number …That is perfect :)

OK, What  is the complexity, as you can see, we have just a one loop , so, complexity will be O(N), as we are using just a one int variable it means we do not use extra memory … Perfect, we solved that task …

Cheers ! :)

Algorithm {The maximum-subarray problem}

Hey,
I’ve just opened Introduction to Algorithms on Divide-and-Conquer chapter, and found interesting item – The maximum-subarray problem. In book you can find implementation with complexity O(NlogN) with good explanation, but in Exercises part there is good task:

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1..j] , extend the answer to find a maximum subarray ending at index j+1 by using the following observation: a maximum subarray of A[1..j+1] is either a maximum subarray of A[1..j] or a subarray A[i..j+1], for some 1<=i<=j+1. Determine a maximum subarray of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index j .

So, That is easy, because there are some ideas, you just need to stop and think a bit and all will be clear …

As described in the book you need to return 3 params
– max sum
– start index of sub array
– end index of sub array

OK, lets go …

Firstly create return structure.

public class SubArrayResult {
        final long sum;
        final int startIndex;
        final int endIndex;
 
        private SubArrayResult(long sum, int startIndex, int endIndex) {
            this.sum = sum;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }
 
        public long getSum() {
            return sum;
        }
 
        public int getStartIndex() {
            return startIndex;
        }
 
        public int getEndIndex() {
            return endIndex;
        }
 
        @Override
        public String toString() {
            return "SubArrayResult{" +
                    "sum=" + sum +
                    ", startIndex=" + startIndex +
                    ", endIndex=" + endIndex +
                    '}';
        }
    }

After that try to create algorithm.

public SubArrayResult findMaximumSubArray(int[] A) {
        long sum = 0;
        long result = 0;
        int start = 0;
        int end = 0;
 
        for (int i = 0; i < A.length; i++) {
            if (sum == 0 && A[i] <= 0) {
                start = i + 1;
                continue;
            }
            sum += A[i];
            if (sum > result) {
                end = i;
                result = sum;
            }
            if (sum < 0) {
                start = i + 1;
                sum = 0;
            }
 
        }
        return new SubArrayResult(result, start, end);
    }

OK, what algorithm is doing:

- firstly run throughout all array

for (int i = 0; i < A.length; i++)

- skipping negative values and move start index

if (sum == 0 && A[i] <= 0) {
   start = i + 1;
   continue;
}

- just add next value to current sum 

sum += A[i];

- check if current sum > result value, if yes, assign sum to result and move end to current index

if (sum > result) {
 end = i;
 result = sum;
}

- and last one if sum < 0 assign 0 to sum and move start to next index

if (sum < 0) {
  start = i + 1;
  sum = 0;
}

So, that is all :)