Tag Archives: algorithms

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

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
	
	doSum = function(a, b, cary) {
		var _cary = 0;
		var sum = a + b + cary;
		if(sum == 10) {
		  sum = 0;
		  _cary = 1;
		}
		else if(sum > 10) {
		  sum = sum - 10;
		  _cary = 1;			
		}
		return  {
			'sum' : sum,
			'cary' : _cary

		}		
	}
		

	var nodeA = l1;
	var nodeB = l2;
	var cary = 0;
	var sum = 0;
	var result = null;
	var lastNode = null;


	while(nodeA != null || nodeB != null) {

		var a = nodeA ?nodeA.val : 0;
		var b = nodeB ?nodeB.val : 0;
		sumResult = doSum(a, b, cary);
		node = new ListNode(sumResult.sum);
		cary = sumResult.cary;

		if(result == null) {
			result = node;
		}
		else {
			lastNode.next = node;
		}
		lastNode = node;

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

	}
	if(cary > 0) {
		node.next = new ListNode(cary);
	}
	return 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.