Tag Archives: algorithms

Plus One

Task

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input:

 [1,2,3]

Output:

 [1,2,4]

Explanation:

 The array represents the integer 123.

Example 2:

Input:

 [4,3,2,1]

Output:

 [4,3,2,2]

Explanation:

 The array represents the integer 4321.

This problem was taken from Leetcode

Solution

The solution:

The solution is pretty straight forward. We traverse all digits in the opposite direction, and make sure that we add +1 only on the last digit (the first iteration ). Then if the digit > 9 we set up the dit to 0, and we carry on 1 to add it to the next digit, and keep going till we reach the first digit. If the first digit is 9 and cary over is not 0, we add 1 to the beginning of the array.

let’s consider: 9 9 9

iteration 1:
9            9
9            9
9 + 1 =  0 + cary on: 1

iteration 2:
9            9
9 + 1 =  0 + cary on: 1
0            0

iteration 3:
9 + 1 = 0 + cary on: 1
0          0
0          0

finally:
1     << adding leading 1 
0
0
0

which gave up the final result: 1 0 0 0

The solution will look like this:

Java Script

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    
    var carryOn = 0;
    for(q = digits.length - 1; q!=-1; q--) {
        var digit = digits[q];
        if(q == digits.length - 1) {
            digit = digit + 1;
            if(digit == 10) {
                digit = 0;
                carryOn = 1;
            }
        }
        else {
            if(digit == 9 && carryOn) {
                digit = 0;
            }
            else {
                digit = digit + carryOn;
                carryOn = 0;
            }
        }
        digits[q] = digit;
    }
    if(carryOn > 0) 
        digits.unshift(1);
    return digits;
};

 

what we just did:
– (lines 11 – 18) happened only if this is the last digit, where we have to add 1
– (lines 18 – 20) if we have carry on value of carryOn > 0 and digit = 9 simply set digit = 0 and left carryOn to be equal to 1 for the next iteration.

Valid Parentheses

Task

Given a string containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input:

 "()"

Output:

 true

Example 2:

Input:

 "()[]{}"

Output:

 true

Example 3:

Input:

 "(]"

Output:

 false

Example 4:

Input:

 "([)]"

Output:

 false

Example 5:

Input:

 "{[]}"

Output:

 true

This problem was taken from Leetcode

Solution

The solution:

Let’s look at the simplest scenario where we have only one type of brackets: ‘(‘ and ‘)’. Then all that we need to do in order to figure out if each bracket has corresponding closing bracket is to put each opening bracket into a stack, and pop one bracket when we see closing bracket.

Ideally if the brackets are “normalized” (all of the open one have corresponding closing brackets) we will end up with empty stack.

in example :

( ( ) ( ) ( ( ) ) )
1 2  3  4 5  6  7  8  9  10

so here are all 10 steps:

steps  stack
1          (
2          (  (
3         (
4         (  (
5         (
6         (  (
7         (  (  (
8         (  (
9         (
10

Immediately it becomes clear that if the string  length is not an even number, it automatically becomes invalid. So we could do this check in the very beginning (lines 9 and 10)  below.

So let’s look at the current example where we have 3 different tags: ‘{}’, ‘()’, ‘[]’

The rule for a valid string is:
open tags:
– we could have as many open tag as we want. i.e. : ({[[ ...
closing tags:
– every closing tag should match previously opened tag ([]) – valid, ([)] – invalid.

So now we know the rules, let’s write the code.

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    
    var input = s.split('');
    
    if(input.length % 2 != 0)
        return false;
    
    var stack = [];

    var tagIndex = {
        '(': 0,
        ')': 1,
        '{': 2,
        '}': 3,
        '[': 4,
        ']': 5
    };        


    for(var q=0;q < input.length; q++) {
        var symbol = input[q];
        var tagType = (tagIndex[symbol] % 2); // 0 - open, 1 - close
        if(tagType == 0) {
            stack.push(symbol);
        }
        else {
            // this is a closing tag, make sure that it follows the rules
            lastTag = stack.pop();            
            lastTagIndex = tagIndex[lastTag];
            if( tagIndex[symbol] != lastTagIndex + 1 )
                return false;
        }
    }
    
    if(stack.length > 0)
        return false;
    return true;
};

 

what we just did:
– lines 9 and 10: we check if the length of the string is odd and return false immediately if so.
– we added tagIndex object where every bracket has it’s index which will help us to identify if we have the open or closing bracket.
– If it is open bracket, we just putting it inside the stack.
– if this is a close bracket, we are using the newly created  tagIndex to figure out if this is the right closing bracket from the same type. Simply following the rule that we described above (lines 32 -35)  `if( tagIndex[symbol] != lastTagIndex + 1 )` Basically we check if the previous opening tag in the stack is of the same type of the current closing tag.

Median of Two Sorted Arrays

Task

Task:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

This problem was taken from Leetcode

Solution


Using a brute force we could merge the two arrays and find the median, but this is slow.
To optimize the solution we could use one of the properties of the arrays: the arrays are sorted.
– We could substitute the problem of find the median with find the numbers that are not in the median

Two sum diagram

The solution:

Java Script

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {

	function findMedianIndex(arr) {
		var median = 0;
		var i = 0;
		if(arr.length % 2) {
			var i = (arr.length / 2 + 0.5) - 1;
			median = arr[i];
		}
		else {
			var i = (arr.length / 2);
			median = ((arr[i - 1] + arr[i]) / 2);
		}
		return median;
	}

	function isFirstArrayInTheMiddleOfSecondEvenArray(x, y) {		
		var minX = x[0];
		var maxX = x [1];
		var medianY = Math.floor(y.length / 2);
		var leftMiddleY = y[medianY - 1];
		var rightMiddleY = y[medianY];
		return minX > leftMiddleY && maxX < rightMiddleY; } function findMedianOfArrayAndValue(arr, val) { if(arr.length == 0) { return val; } else if (typeof(val) == 'undefined') { return findMedianIndex(arr); } var median = 0; if(arr.length % 2) { // odd aray // var medianIndex = Math.floor((arr.length / 2)); // median = arr[medianIndex]; var arrMedian = findMedianIndex(arr); if(arrMedian > val) {
				// the median of merged array should lie on the left of arr  <== var i = Math.floor(arr.length / 2); var right = arr[i]; var left = Math.max( arr[i - 1], val ); return findMedianIndex( [left, right] ); } else { // the median of merged array should lie on the right of arr ==>
				var i = Math.floor(arr.length / 2);
				var left = arr[i];				
				var right = Math.min( arr[i + 1], val );
				return 	findMedianIndex( [left, right] );					
			}
		}
		else {
			// even aray
			var arrMedian = findMedianIndex(arr);
			if(arrMedian > val) {
				// the median of merged array should lie on the left of arr median  <== var i = Math.floor((arr.length / 2) - 1); var left = arr[i]; return Math.max(left, val); } else { // the median lies on the right side ==>
				var i = (arr.length / 2);
				var right = arr[i];
				return Math.min(right, val);
			}

			median = findMedianIndex( [ arr[medianIndex], arr[medianIndex + 1] ]);

		}
		return ( Math.min(median, val) + Math.max(median, val) ) / 2;
	}


	function findMedian(X, Y) {

		// check all odd cases	
		if (X.length === 1 && Y.length === 1) {
			return (X[0] + Y[0]) / 2;
		}

		if(X.length <= 1) {
			return findMedianOfArrayAndValue(Y, X[0]);
		}
		else if(Y.length <= 1) {
			return findMedianOfArrayAndValue(X, Y[0]);
		}		
		else if(X.length == 1 && Y.length == 1) {
			var testArray = [ X[0], Y[0] ];
			return findMedianIndex(testArray);
		}
		else if(X.length < 1) {
			var testArray = Y.concat(X);
			return findMedianIndex(testArray);	
		}
		else if( Y.length < 1) { var testArray = X.concat(Y); return findMedianIndex(testArray); } if( X.length === 2 && Y.length >= 2 && Y.length % 2 === 0) {
			if(isFirstArrayInTheMiddleOfSecondEvenArray(X, Y)) {
				/*
					in example:
					var X = [1, 2];
					var Y = [-1, 3];
				*/
				return (X[0] + X[1]) / 2;
			}
		}
		if( Y.length === 2 && X.length >= 2 && X.length % 2 === 0) {
			if(isFirstArrayInTheMiddleOfSecondEvenArray(Y, X)) {
				/* and the other way */
				return (Y[0] + Y[1]) / 2;
			}
		}	

		var mX = findMedianIndex(X);
		var mY = findMedianIndex(Y);
		
		if(mX == mY) {
			return mX;
		}
			

		var splicePart = Math.floor(Math.min(X.length / 2 - 1, Y.length / 2 - 1));
		splicePart = splicePart < 1 ? 1 : splicePart;

		if (mX < mY) {
			X.splice(0, splicePart);
			Y.splice(Y.length - splicePart);
		} else {
			X.splice(X.length - splicePart);
			Y.splice(0, splicePart);
		}
	

		return findMedian(X, Y);
	}

	return findMedian(nums1, nums2);
}

Two Sum

Task

Task:
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Examples :

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

This problem was taken from Leetcode

Solution

One pass hash table.

Let’s take this example: nums = [2, 7, 11, 15], target = 9
The brute force solution might be to loop through each value in the nums array, and to add with each other value in the array and to compare with the target result.

Optimize the algorithm using hash table

The idea is to store the array into a hash table where keys will be the values of the array (i.e: 2, 7, 11, 15) and the values: the element index (i.e: 0,1,2,3)
key:value
2 : 0,
7 : 1,
11:2,
15:3

Two sum diagram

This way all we need to do is:
– Iterate through the array once.
– For each value calculate what number could add to the target value ( x = target – nums[i])
– Dynamically add the next key-value pair into the hashmap

The solution:

Java Script

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var hashMap = {};


    for(var i in nums) {                
            
        var test = target - nums[i];
        if(hashMap[test]) {
            return [parseInt(hashMap[test]), parseInt(i)];
        }     
        var key = nums[i];
        hashMap[key] = i;   
    }
};

C++

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        vector<int> result;

        std::map<int, int> buffer;
        for(int i = 0;i < nums.size(); i++) {
            int key = nums[i];
            int test = target - nums[i];

            if(buffer[test] != 0) {
                result = {buffer[test] -1, i};
                break;
            }
            buffer[key] = i + 1;
        }
        return result;
    }
};

 

Longest Substring Without Repeating Characters

Task

Task:
Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", which the length is 3.

 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

 

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

 

This problem was taken from Leetcode

Solution

The sliding window solution.

The sliding window represents a range of elements like an array,  defined by the start and end indices. Then we start moving “sliding” the indices to the next checked subset.

Let’s say that we have this string: “ABCDECFGH”.
The answer of the problem is “DECFGH“.

The obvious resolution could be to grab each letter of the string (starting with the first one), compare it with a buffer of the letters that we already checked and if there is match, continue with the next letter and keep track of the length of the longest string sequence without repeated characters.

In the current example “ABCDECFGHlet’s name is S we start with starting index i  = 1, and end index j = 1. so S[i, j)

Then we start “sliding” j adding more elements in the range and comparing next element added in the range with all previous elements till we find match. I our example this will happen on i = 1 and j = 6 since 6th letter is C and C is already in the range at position 3. Let’s call it j1 = 3.

Then the next step will be to “slide” i and start all over. i = i + 1.

But we could improve this algorithm in two ways:

  1. Store the characters in the buffer into an associative array or so called hashmap where the key will be the character, and the value the index. Example:
    { key = A, val = 1 }
    { key = B, val = 2 }

    This way we don’t have to iterate through each element into the buffer when checking if the character is there or not.
  2. When we find match, we don’t have to start from the next character but we can “slide” to the value of the character in the buffer that matched + 1 since we already know, that the sequence before has shorter length.
    In the range [i, j1] which in the current example is [1, 3] we know for sure that there will be no substring longer than the current one [i, j] so we don’t have to “slide” i = i + 1 but we could do i = j1 + 1 which will save checking of [i+1, j1]  (B and C)
    Example:
    start checking ABCDE and then C is already found in the buffer at index = 3. So instead of starting from index 2 – B we could start from index 3 + 1 which is D

Longest Substring Without Repeating Characters solution diagram

The solutions:

Java Script

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {


    var hashMap = {};    

    function findUniqueSequence(left) {
        var buffer = [];
        
        for(var c = left;c < s.length; c ++) {            
            if(buffer.includes(s[c])) {
                var symbol = s[c];
                var nextPos = hashMap[symbol] + 1;
                return [buffer, nextPos ];
            }
            hashMap[s[c]] = c;
            buffer.push(s[c]);
        }
        return [buffer, s.length];
    }


    var left = 0; 
    var longest = [];       
    while(left < s.length) {
        var result = findUniqueSequence(left);
        left = result[1];
        longest = longest.length < result[0].length ? result[0] : longest;
        if(s.length - left < longest)
            break;
    }
    return longest.length;    
};

 

C++

class Solution {
    
public:
    int lengthOfLongestSubstring(string s) {
        unsigned long n = s.length();
        char char_array[n+1];
        strcpy(char_array, s.c_str());
        
        int left = 0;
        unsigned long arr_length = sizeof(char_array) - 1;
        int longestStringSize = 0;
        int sizeCounter = 0;
        
        std::map<char, int> buffer;
        int co = 0;
        while (left < arr_length) {
            char cursor = char_array[left];
            
            if(buffer[cursor] == 0) {
                buffer[cursor] = left + 1;
                sizeCounter ++;
                left ++;
            }
            else {
                left = buffer[cursor];
                buffer.clear();
                longestStringSize = sizeCounter > longestStringSize ? sizeCounter : longestStringSize;
                sizeCounter = 0;
            }
        }
        longestStringSize = (longestStringSize == 0 || sizeCounter > longestStringSize) ? sizeCounter : longestStringSize;
        return longestStringSize;
    }
};

 

Add Two Numbers

Task

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Examples :

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

This problem was taken from Leetcode

Solution

The solution:

Java Script

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */



function ListNode(val, next) {
  this.val = (val===undefined ? 0 : val)
  this.next = (next===undefined ? null : next)
}


/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  
  function doSum(a,b, carry) {
    var result = {
      val: 0,
      carry: 0
    }
    var sum = a + b + carry;
    if(sum > 9) {
      result.val = sum - 10;
      result.carry = 1;
    }
    else {
      result.val = sum;
      result.carry = 0;
    }
    return result;
  }

  var nodeA = l1;
  var nodeB = l2;
  var end = false;
  var carry = 0;
  var result = new ListNode(0, null);
  var resultPointer = result;
  var tmp = null;

  while(nodeA != null || nodeB != null) {
    var valA = nodeA == null ? 0 : nodeA.val;
    var valB = nodeB == null ? 0 : nodeB.val;
    var sumResult = doSum(valA, valB, carry);
    carry = sumResult.carry;
    
    resultPointer.val = sumResult.val;
    resultPointer.next = new ListNode(0, null);
    tmp = resultPointer;
    resultPointer = resultPointer.next;

    nodeA = nodeA ? nodeA.next : null;
    nodeB = nodeB ? nodeB.next : null;
  }

  if(carry != 0) {
    tmp.next.val = carry; // add carry to the val of the last node
  }
  else 
    tmp.next = null; // remove the last empty node.
  return result;
};




var l1 = new ListNode(9, 
          new ListNode(9,
          new ListNode(9,
          new ListNode(9, null)
      ))
);

var l2 = new ListNode(9, 
          new ListNode(9,
          new ListNode(9,
          new ListNode(9,
          new ListNode(9,
          new ListNode(9,                    
          new ListNode(9, null)
      )))))
)

// [9,9,9] , [9,9,9,9,9]
// result: [8,9,9,0,0,1]

var result = addTwoNumbers(l1, l2);

console.log(result);

Climbing stairs

Task

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.


Example 1:

Input: 2
Output: 2

Explanation:

 There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps


Example 2:

Input: 3
Output: 3

Explanation:

 There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

 

This problem was taken from Leetcode

Solution

The solution:

Let’s look at the possible scenarios:

# of stairsways to climb# of ways to climb
111
21 1
2
2
31 1 1
2 1
1 2
3
41 1 1 1
2 1 1
1 2 1
1 1 2
2 2
5
51 1 1 1 1
2 1 1 1
1 2 1 1
1 1 2 1
1 1 1 2
2 2 1
2 1 2
1 2 2
8
61 1 1 1 1 1
2 1 1 1 1
1 2 1 1 1
1 1 2 1 1
1 1 1 2 1
1 1 1 1 2
2 2 1 1
1 2 2 1
1 1 2 2
2 1 1 2
2 1 2 1
1 2 1 2
2 2 2
13
71 1 1 1 1 1 1
2 1 1 1 1 1
1 2 1 1 1 1
1 1 2 1 1 1
1 1 1 2 1 1
1 1 1 1 2 1
1 1 1 1 1 2
2 2 1 1 1
1 2 2 1 1
1 1 2 2 1
1 1 1 2 2
2 1 2 1 1
2 1 1 2 1
2 1 1 1 2
1 2 1 1 2
1 1 2 1 2
1 2 1 2 1
2 2 2 1
1 2 2 2
2 1 2 2
2 2 1 2
21

If we look at the # of ways to climb, we clearly see that the ways to climb grows in Fibonacci sequence: 1, 2,  3,  5,  8,  13, 21

Then all we need to do is to iterate n times (where n  is the number of stairs) and to find the corresponding Fibonacci number.

Using while loop

  • basically we use temp to store previous Fibonacci number temp = a , initially 1
  • then we calculate the next number a = a + b , initially a = 0 + 1
  • then we set up b = temp which stores the last Fibonacci number in order to be ready for the next iteration. Initially 1.

Looking at the numbers from the first iteration, it is clear that on the second one we will have:
temp = a = 1
a = a + b = 1 + 1 = 2
b = temp = 1

third iteration will produce:
temp = a = 2
a = a + b = 2 + 1 = 3
b = temp = 2
forth iteration:
temp = a = 3
a = a + b = 3 + 2 = 5
b = temp = 3

and so on … a will always return the Fibonacci number for the current n position.

Java Script

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if( n < 4) 
        return n;

    fibonacci = function(n) {

        var a = 1, b = 0, temp, num = 1;

        while(num <= n) {
            temp = a;
            a = a + b;
            b = temp;
            num ++;
        }
        return a;
    }

    return fibonacci(n);
};

Using For loop

This is the easiest to comprehend:

  • we create an array to store the Fibonacci numbers var fn = [1,1] with the first two numbers pre-set so the for loop could generate the next one.
  • created for loop that picks the fn[i - 1] and fn[i - 2] numbers and generate the next one.
  • pushed newly calculated Fibonacci number into an array so we could use to generate next one.
  • keep looping till we reached i < n + 1 which is the  answer.

Java Script

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if( n  < 3)
    return n;
    
    var fn = [1,1];
    for(var i = 2; i < n + 1; i ++) {
        var nextNumber = fn[i - 1] + fn[i - 2]; 
        fn.push(nextNumber);
    }

    return fn[fn.length - 1];
};

 

Third solution: Using recursive function.

Java Script

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if( n < 4) 
        return n;

    fibonacci = function(n) {
        if(n < 2) {
            return n;
        }
        var result = fibonacci(n - 1) + fibonacci(n - 2);        
        return result;
    }

    return fibonacci(n + 1);
};

The idea here is to call fibonacci(n) function to generate the next Fibonacci number.
For n < 2 the function will simply return n 0,1,2.
For n = 3 the function will call itself recursively asking for previous two Fibonacci numbers (2 and 1) and will calculate the next number which is the sum of the previous two, and so on.

Optimize the recursive function to use Memoization.

Memoization is simple technique where we are storing the value of already computed parameter into a HashMap function and quickly retrieve it when we need it.

In our current example since the keys are just a numbers we could store the Fibonacci numbers in a regular array (line 9). Then we simply check if the value already is set up into memo array and return it or call fibonacci function once again.
Then we set up memo array with the next solved Fibonacci number with index n

Java Script

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if( n < 4) 
        return n;

    var memo = [];
    fibonacci = function(n) {
        if(n < 2) {
            return n;
        }
        var a = memo[n - 1] ? memo[n - 1] : fibonacci(n - 1);
        var b = memo[n - 2] ? memo[n - 2] : fibonacci(n - 2);

        return memo[n] = a + b;
    }

    return fibonacci(n + 1);
};

 

You might also want to check Fibonacci sequence generator.