Tag Archives: algorithms

Trapping Rain Water

Task

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.


image was borrowed from leetcode

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input:

 [0,1,0,2,1,0,1,3,2,1,2,1]

Output:

 6

This problem was taken from Leetcode

Solution

 

The brute force approach: for each element we go to the right and find the maximum height of the bar, then we go to the left and do the same.

For any element the maximum amount of the water that could be trapped will be the minimum of left height and right height, minus the height of the bar.

So for the array [0,1,0,2,1,0,1,3,2,1,2,1] we go all the way to the right and calculate the max right value, starting from first element ‘0’ max right will be 0. ‘1’ – max right is ‘1’ and so on.
We repeat the same from last element ‘1’ to the first one.

Then the trapped water for the first column will be:  min(maxRight, maxLeft) – theArrayElement[n]

the array 0 1 0 2 1 0 1 3 2 1 2 1
max right 0 1 1 2 2 2 2 3 3 3 3 3
max left 3 3 3 3 3 3 3 3 2 2 2 1
collected
water
0 0 1 0 1 2 1 0 0 1 0 0

 

The complexity will be O(n2)

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    if(height.length < 2)
        return 0;

    let findMaxLeft = function(idx, height) {
        let max = 0;
        for(let i =idx;i >= 0; i --) {
            max = Math.max(max, height[i]);
        }
        return max;
    }

    let findMaxRight = function(idx, height) {
        let max = 0;
        for(let i = idx;i < height.length; i ++) {
            max = Math.max(max, height[i]);
        }
        return max;
    }  

    let collectedWater = 0;
    for(let i = 0;i < height.length; i ++) {

        const maxLeft = findMaxLeft(i, height);
        const maxRight = findMaxRight(i, height);

        let min = Math.min(maxLeft, maxRight);
        collectedWater += (min - height[i]);
    }

    return collectedWater;
};

The better solution: find all max left and max right with one loop, then do a second loop for each element in the array, and calculate trapped water.

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let maxLeftArray = [], maxRightArray = [];
    let maxLeft = 0, maxRight = 0;
    const ln = height.length;
    let trappedWater = 0;

    for(let i = 0;i < height.length; i ++) {
        maxLeftArray[i] = Math.max(height[i], maxLeft);
        maxLeft = maxLeftArray[i];

        maxRightArray[ln - i - 1] = Math.max(height[ln - i - 1], maxRight);
        maxRight = maxRightArray[ln - i - 1];
    }

    for(let i = 0;i < height.length; i ++) {
        trappedWater += Math.min(maxLeftArray[i], maxRightArray[i]) - height[i];
    }
    return trappedWater;

};
what we just did:

– With one loop find the max left and right bar on each side.
– for any element the maximum amount of the water that could be trapped will be the minimum of left height and right height, minus the height of the bar.

Array VS Hash Table

Hash table tutorial

Find element in Array

function fuindInArray() {
  var t0 = performance.now();

  for(var q = 0; q < data2.length; q++) {
      if( data2[q] == '106112407') {
          console.log(data2["106112407"]);
          break;
      }
  }

Find element in Hash Table

function findInHashtable() {
  var t0 = performance.now();

  console.log(data1["106112407"]);

  var t1 = performance.now();
  document.querySelector('#result1').value = "Call took " + (t1 - t0) + " milliseconds.";
}

 


Majority element in array

Task

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input:

 [3,2,3]

Output:

 3

Example 2:

Input:

 [2,2,1,1,1,2,2]

Output:

 2

This problem was taken from Leetcode

Solution

The solution:

Create an object (or associative array, depends of the language), iterate through all elements in the array adding them to the newly created object using the element value as a key. If element exists increase the value +1.
Keep track of mostly repeated element and return it at the end.

var arr = [3, 3, 4, 2, 4, 2, 4, 4];


/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  var elements = {};
  var majorityElement = nums[0];
  var majorityElementCount = 1;
  for(var i in nums) {
  	var element = nums[i];
  	elements[element] = typeof elements[element] == 'undefined' ? 1 : elements[element] + 1;
  	if(elements[element] > majorityElementCount) {
  		majorityElement = element;
  		majorityElementCount = elements[element];
  	}
  }    
  return majorityElement;
};

console.log(">>", majorityElement(arr));

– Create an object (line 9)
– Iterate through each element in the array feeling up the object with the elements from the array where the element value would be the key of the element (line 14)
– Each time when the element exists, add + 1
– Keep track of mostly repeated element (Lines 16-17)

Could we optimize the code? Slightly. When we add + 1 we could check if the value is already greater than the length of the array / 2 and if se we know that this is the majority element because no other element could have greater value.

...
    if(elements[element] > nums.length / 2) {
        return element;
    }
...

 

Maximum Subarray

Task

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input:

 [-2,1,-3,4,-1,2,1,-5,4],

Output:

 6

Explanation:

 [4,-1,2,1] has the largest sum = 6.

This problem was taken from Leetcode

Solution

The solution:

Brut force.

The straight forward solution could be to iterate through all elements in the array and calculate the subarray values and compare them.

In the example above[-2,1,-3,4,-1,2,1,-5,4] we will do:

starting index: 1
-2 = -2
-2, 1 = -1
-2, 1, -3 = -4
-2, 1, -3, 4 = 0
-2, 1, -3, 4, -1 = -1
-2, 1, -3, 4, -1, 2 = 1
-2, 1, -3, 4, -1, 2, 1 = 2
-2, 1, -3, 4, -1, 2, 1, -5 = -3
-2, 1, -3, 4, -1, 2, 1, -5, 4 = 1

starting index: 2
1 = 1
1, -3 = -2
1, -3, 4 = 2
1, -3, 4, -1 = 1
1, -3, 4, -1, 2 = 3
1, -3, 4, -1, 2, 1 = 4
1, -3, 4, -1, 2, 1, -5 = -1
1, -3, 4, -1, 2, 1, -5, 4 = 3

starting index: 3
-3 = -3
-3, 4 = 1
-3, 4, -1 = 0
-3, 4, -1, 2 = 2
-3, 4, -1, 2, 1 = 3
-3, 4, -1, 2, 1, -5 = -2
-3, 4, -1, 2, 1, -5, 4 = 2

starting index: 4
4 = 4
4, -1 = 3
4, -1, 2 = 5
4, -1, 2, 1 = 6
4, -1, 2, 1, -5 = 1
4, -1, 2, 1, -5, 4 = 5

… and so on till the last element in the array.

So the winner clearly is 4, -1, 2, 1 = 6, but this approach will take a lot of repetitions. Interestingly there is a linear solution called: Kadane’s algorithm.

Using Kadene’s algorithm.

The basic idea of this algorithm is to break the array into a sets of mutually exclusive sets, calculate their sums and find the largest one.

First let’s look closely of what we are doing to find the maximum sum using brut force. We are splitting the array to a sets of all possible contiguous sub arrays and we calculate their sum. This means that:
– if the array contains only negative values we don’t really need to split the array cause the answer will be the largest value in the array. i.e. [-1,-5,-3] = -1 (the one close to 0)
– if this is a mixed array with negative and positive values the max sum of contiguous sub array will be > 0 so we could ignore any case where the sum is negative.

This way we could iterate through each element of the array nums[i]  where i is the index of the element in the array (starting with the first one nums[0]), and calculate the sum (let’s call it max_here = max_here + nums[i] ).
If we get a negative result we already know for sure that this is not what we are looking for and we set up max_here to the next element in the array max_here = nums[i]

So in the example above: [-2,1,-3,4,-1,2,1,-5,4]
We are starting by setting up both params to the first element in the array: max_here =max_so_far = nums[0] . We are going to use max_so_far to store the maximum sum discovered so far, and max_here to calculate the maximum sum so far. Once again if the max_sum is negative, we just set it up to be equal to the next element in the array nums[i] so on the next iteration max_sum = nums[i-1] + nums[i]

Starting with setting up max_here = max_so_far = nums[0] = -2

i nums[i]    action described max_here max_so_far
1 1  sum = max_here + nums[1], which is:
sum = -2 + 1 = -1 which is smaller than nums[1] so max_here = nums[1] = 1 (line 10 in the code snipped below)
and since max_here > max_so_far,  max_so_far = max_here =1 (line 11)
1 1
2 -3  sum = max_here + nums[2] which is:
sum = 1 + (-3) = - 2 which is bigger than nums[2] which is -3 so max_here = sum = -2But max_here is smaller than max_so_far so max_so_far stays equal to 1
-2 1
3 4  sum = -2 + 4 = 2 which is < than 4 so  max_here = nums[4] = 4 which is > max_so_far so max_so_far = max_here = 4 4 4
4 -1   sum = 4 - 1 = 3 > – 1 so
max_here = sum = 3
3 4
5 2  sum = 3 + 2 = 5
which is > than nums[5] = 2 so
max_here = max_so_far = sum = 5
5 5
6 1  sum = 5 + 1 = 6
which is > than nums[6] = 1 so
max_here = max_so_far = sum = 6
6 6
7 -5  sum = 6 + (-5) = 1
which is > than nums[7] = -5 so
max_here = 1
1 6
8 4  sum = 1 + 4 = 5
which is > than nums[8] = 4 so
max_here = 5 but
max_here < max_so_far so
max_so_far stays the same: 6 which is the maximum sum here.
5 6

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    var max_here = max_so_far = nums[0];
    

    for(var i=1;i < nums.length; i ++) {
        max_here = Math.max(max_here + nums[i], nums[i]);
        max_so_far = Math.max(max_so_far, max_here);
    }    

    return max_so_far;
};

 

 

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);