Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input:

 haystack = "sadbutsad", needle = "sad"

Output:

 0

Explanation:

 "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input:

 haystack = "leetcode", needle = "leeto"

Output:

 -1

Explanation:

 "leeto" did not occur in "leetcode", so we return -1.

Constraints:

• 1 <= haystack.length, needle.length <= 10⁴
• haystack and needle consist of only lowercase English characters.

this problem was taken from Leetcode

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    var match = 0;

    // Edge case: if needle is an empty string, return 0
    if (needle === "") {
        return 0;
    }

    // Get the lengths of both strings
    const haystackLen = haystack.length;
    const needleleLen = needle.length;
    
    // Iterate through the haystack string
    for (let i = 0; i <= haystackLen - needleleLen; i++) {
        var left = 0;
        while(left < needleleLen && haystack[left + i] == needle[left]) {
            left ++;
        }
        if(left == needleleLen) {
            return i;
        }
    }
    return -1;
};

Explanation:

1. Edge Case: If needle is an empty string, the function immediately returns 0.
2. Outer Loop: The outer loop iterates over each character in haystack where there is still enough remaining length to match the needle (i <= haystackLen - needleLen).
3. Inner Loop: The inner loop checks if the substring of haystack starting at i matches needle. It does this by comparing characters one-by-one.
4. Match Found: If a match is found (j === needleLen), the starting index i is returned.
5. No Match: If no match is found by the end of the loop, the function returns -1.

This implementation mimics a basic substring search without using any built-in functions. The time complexity is O(n * m), where n is the length of haystack and m is the length of needle.

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input:

 nums = [-1,2,1,-4], target = 1

Output:

 2

Explanation:

 The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input:

 nums = [0,0,0], target = 1

Output:

 0

Explanation:

 The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints:

• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -10⁴ <= target <= 10⁴

this problem was taken from Leetcode

Explanation:

1. Sorting the array: This is necessary so that we can use the two-pointer technique effectively.
2. Two pointers: For each element, we use two pointers to explore possible sums by adjusting their positions.
3. Closest sum: We keep track of the closest sum throughout the iteration and update it whenever we find a sum closer to the target.

Check 3 Sum approach for more details.

function threeSumClosest(nums, target) {
    // Sort the array first
    nums.sort((a, b) => a - b);
    let closestSum = Infinity;

    // Iterate through the array
    for (let i = 0; i < nums.length - 2; i++) {
        let left = i + 1;
        let right = nums.length - 1;

        // Use two pointers to find the best sum
        while (left < right) {
            let currentSum = nums[i] + nums[left] + nums[right];

            // Update the closest sum if needed
            if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                closestSum = currentSum;
            }

            // Move the pointers based on the current sum
            if (currentSum < target) {
                left++;
            } else if (currentSum > target) {
                right--;
            } else {
                // If the exact sum is found, return immediately
                return currentSum;
            }
        }
    }

    return closestSum;
}

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input:

 nums = [-1,0,1,2,-1,-4]

Output:

 [[-1,-1,2],[-1,0,1]]

Explanation:

 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input:

 nums = [0,1,1]

Output:

 []

Explanation:

 The only possible triplet does not sum up to 0.

Example 3:

Input:

 nums = [0,0,0]

Output:

 [[0,0,0]]

Explanation:

 The only possible triplet sums up to 0.

this problem was taken from Leetcode

Explanation:

1. Sorting the Array: The array is first sorted to easily manage duplicates and use a two-pointer approach.
2. Iterating with a Loop: A loop iterates through the array, fixing one element (nums[i]) and then using a two-pointer approach to find the other two elements (nums[left] and nums[right]).
3. Avoiding Duplicates: Duplicate values are skipped using continue for the first element and while loops for the second and third elements to ensure the solution set contains only unique triplets.
4. Two-Pointer Approach: The sum is checked, and pointers are adjusted accordingly to find valid triplets.

Example Usage:

This would output:

This solution efficiently finds all unique triplets that sum to zero in O(n^2) time complexity.

Skipping duplicates in the threeSum algorithm is crucial to ensure that the solution set contains only unique triplets. Here’s a detailed explanation of how duplicates are skipped at different stages:

1. Skipping Duplicates for the First Element (i):

When iterating through the array with the outer loop (for (let i = 0; i < nums.length - 2; i++)), the algorithm checks if the current element nums[i] is the same as the previous element nums[i - 1]. If they are the same, it means that any triplet starting with this element would already have been considered in a previous iteration, so the algorithm skips this iteration.

Code Example:

Explanation:

• i > 0: Ensures that we don’t check for a previous element when i is 0.
• nums[i] === nums[i - 1]: If this condition is true, it means nums[i] is a duplicate of the previous element, so the loop skips to the next i using continue.

2. Skipping Duplicates for the Second and Third Elements (left and right):

After fixing the first element nums[i], the algorithm uses two pointers, left and right, to find the other two elements (nums[left] and nums[right]) that, together with nums[i], sum to zero.

Once a valid triplet is found, the algorithm moves both pointers inward but also checks for duplicates by comparing the current elements with the next ones in line. If the next element is the same as the current one, the algorithm skips the next element by advancing the pointer further.

Code Example:

Explanation:

• Left Pointer:
  • while (left < right && nums[left] === nums[left + 1]) left++;
  • This loop skips all duplicate values for nums[left] by incrementing left until it points to a new value.
• Right Pointer:
  • while (left < right && nums[right] === nums[right - 1]) right--;
  • Similarly, this loop skips all duplicate values for nums[right] by decrementing right until it points to a new value.

Why This is Important:

• Avoiding Redundant Triplets: Without skipping duplicates, the algorithm would include multiple instances of the same triplet in the result, which is inefficient and incorrect for this problem.
• Efficiency: Skipping duplicates prevents unnecessary comparisons, speeding up the algorithm.

Example Walkthrough:

Consider the array [-1, 0, 1, 2, -1, -4]:

1. Sorting: The array becomes [-4, -1, -1, 0, 1, 2].
2. Iteration with i = 0 (nums[i] = -4):
   • No duplicates for nums[i], proceed with left = 1 and right = 5.
   • No valid triplet is found, move to the next i.
3. Iteration with i = 1 (nums[i] = -1):
   • Triplet [-1, -1, 2] is found.
   • Skip duplicates: left moves from index 2 to 3 because nums[2] === nums[3].
   • Triplet [-1, 0, 1] is found.
4. Iteration with i = 2 (nums[i] = -1):
   • Skip this iteration entirely because nums[2] === nums[1].

As a result, only unique triplets are returned: [[-1, -1, 2], [-1, 0, 1]].

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) =>{ return a - b });
    const result = [];

    for(let i = 0; i < nums.length - 2; i ++) {
        // Skip duplicate values for the first element of the triplet
        if (i > 0 && nums[i] === nums[i - 1]) {
          continue;
        }
        let left = i + 1;
        let right = nums.length - 1;

        while(left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if(sum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                 // Skip duplicate values for the second and third elements of the triplet
                while (left < right && nums[left] === nums[left + 1]) {
                  left++;
                }
                while (left < right && nums[right] === nums[right - 1]) {
                  right--;
                }
                left ++;
                right --;
            } else if(sum < 0) {
                left ++;
            } else {
                right --;
            }
        }
    }
    return result;
};

Implement pow(x, n), which calculates x raised to the power n (i.e., xⁿ).

Example 1:

Input:

 x = 2.00000, n = 10

Output:

 1024.00000

Example 2:

Input:

 x = 2.10000, n = 3

Output:

 9.26100

Example 3:

Input:

 x = 2.00000, n = -2

Output:

 0.25000

Explanation:

 2

^-2

 = 1/2

²

 = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -2³¹ <= n <= 2³¹-1
• -10⁴ <= xⁿ <= 10⁴

This problem was taken from https://leetcode.com/problems/powx-n/

Brute force solution:

Straight forward, but we have to consider negative ranges.

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    
    if(n === 0) {
        return 1;
    }

    var N = n;
    var X = x;
    var result = 1;
    
    if(n < 0) {
        X = 1 / x;
        N = -n;
    }
    
    for(var i = 0; i < N; i ++) {
        result = result * X;
    }  
    return result;
};

Approach 2: Fast Power Algorithm Recursive

• divide n so you immediately cut the computation time in half to logarithmic one.

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    
    function fastPow(x, n) {
        if(n < 1) {
            return 1;
        }
        var half = fastPow(x, Math.floor(n / 2));

        if(n % 2 == 0) {
            return half * half;
        }
        else {
            return half * half * x;
        }
    }
    
    var X = x;
    var N = n;
    if(n < 0) {
        X = 1 / x;
        N = -n;        
    }
    return fastPow(X, N);
    
};

 strs = ["flower","flow","flight"]

 "fl"

 strs = ["dog","racecar","car"]

 ""

 There is no common prefix among the input strings.

This problem was taken from Leetcode Longest Common Prefix

Let’s examine this example:

 strs = ["flower","flow","flight"]

the longest common substring is:

 "fl"

Solution 1: Horizontal scanning

We could assume that the whole word could be the common one so we set prefix = ‘flower’
Then we would compare with the rest words and keep removing last character until prefix becomes empty (meaning no common substring was found) or until we have the common substring.

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    var prefix = strs[0];
    for(var i = 1; i < strs.length; i ++ ) {
        while(strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if(prefix == "")
                return '';
        }
    }
    return prefix;    
};

 what we just did:
– set up prefix to be the whole 1st word strs[0]
– compare prefix with the second word (strs[1]) and if there is no match, remove the last symbol and keep going until it finds match.

Complexity Analysis

• Time complexity : $O(S)$ , where S is the sum of all characters in all strings.In the worst case all $n$ strings are the same. The algorithm compares the string $S1$ with the other strings [S_2 \ldots S_n][S2​…Sn​] There are $S$ character comparisons, where $S$ is the sum of all characters in the input array.
• Space complexity : $O(1)$. We only used constant extra space.

Solution 2: Vertical scanning

Similar but optimized for cases like the one above where we have very short common substring, and we don’t want to scan the whole word.

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    var prefix;    
    for(var i = 0; i < strs[0].length; i ++ ) {
        var c = strs[0][i];
        for(var j = 0; j < strs.length; j++) {
            if(strs[j][i] != c) {
                return strs[0].substring(0, i);
            }
        }
    }
    return strs[0];    
};

 what we just did:
– Iterate through the words like they are in column.
– compare each character (starting with the first one) between all words. When we find a mismatch, remove the last (mismatched) character and return truncates strs[0]

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol                Value

I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input:

 s = "III"

Output:

 3

Example 2:

Input:

 s = "IV"

Output:

 4

Example 3:

Input:

 s = "IX"

Output:

 9

Example 4:

Input:

 s = "LVIII"

Output:

 58

Explanation:

 L = 50, V= 5, III = 3.

Example 5:

Input:

 s = "MCMXCIV"

Output:

 1994

Explanation:

 M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

This problem was taken from Leetcode Roman To Integer

Solution 1: Left to right pass

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var len = s.length;
    var i = 0;
    var map = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    var sum = 0;
    while(i < len) {
        var currentVal = map[ s[i] ];
        var nextVal = map[ s[i + 1] ];
        if( currentVal < nextVal) {
            sum += nextVal - currentVal;
            i ++;            
        }
        else {
            sum += currentVal;
        }
        i ++;
    }
    return sum;
};

Solution 2: Left to right (or right to left) pass improved

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var len = s.length;
    var i = 0;
    var map = {
        'I': 1,
        'IV': 4,
        'V': 5,
        'IX': 9, 
        'X': 10,
        'XL': 40,
        'L': 50,
        'XC': 90,
        'C': 100,
        'CD': 400,
        'D': 500,
        'CM': 900,
        'M': 1000
    }
    var sum = 0;
    while(i < len) {
        var currentVal = map[ s[i] ];
        var nextVal = map[ s[i + 1] ];
        if( currentVal < nextVal) {
            var sumbol = s[i] + s[i+1];
            sum += map[sumbol];
            i ++;            
        }
        else {
            sum += currentVal;
        }
        i ++;
    }
    return sum;
};

Solution3: Right to left pass

In the “subtraction” cases, such as XC, we’ve been updating our running sum as follows:

sum += value(C) - value(X)

However, notice that this is mathematically equivalent to the following:

sum += value(C)
sum -= value(X)

Utilizing this means that we can process one symbol each time we go around the main loop. We still need to determine whether or not our current symbol should be added or subtracted by looking at the neighbour though.

This way we could start from the most right symbol an initialize the sym with it, since every most right symbol will always be added to the sum.

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var len = s.length;
    var i = len - 1;
    var map = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    var sum = map[ s[i] ];
    i --;
    while(i > -1) {
        var currentVal = map[ s[i] ];
        var prevVal = map[ s[i + 1] ];
        if( currentVal < prevVal) {
            sum -= currentVal;          
        }
        else {
            sum += currentVal;
        }
        i --;
    }
    return sum;
};

Given n non-negative integers a₁, a₂, ..., a_n , where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of the line i is at (i, a_i) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

Input:

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

Output:

 49

Explanation:

 The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input:

 height = [1,1]

Output:

 1

Example 3:

Input:

 height = [4,3,2,1,4]

Output:

 16

Example 4:

Input:

 height = [1,2,1]

Output:

 2

This problem was taken from Leetcode Container With Most Water

A better than brute force solution is to use a variation of “sliding doors” algorithm.

Let’s consider this case: [1,3,4,3]. The area with most water will be the one with highest height and length.

To find it we set up two pointers: one at position 0, and one at the end of the array. The amount of water that could be collected here is min(leftPointerValue, rightPointerValue) * length,
where length is rightPointer – leftPointer. Which is 4.

Now it’s clear that if rightPointerValue > leftPointerValue there is no point of keep moving rightPointer because we won’t get any bigger amount of water since it will always be limited by the leftPointerValue (height) and the length will always be smaller than the previous length.

So in this case we will move the leftPointer forward to evaluate the next case.

Here the amount of the water collected is min(leftPointerValue, rightPointerValue) * length which is min(3, 3) * 3 = 9.

Nex we continue evaluating all cases till leftPointer = rightPointer (length = 0), and we didn’t find bigger amount of water collected, so the answer we found on the second evaluation is the right answer: 9.

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {


  var maxArea = 0;
  var pLeft = 0;
  var pRight = height.length - 1;
  var len = pRight - pLeft;

  while(len > 0) {
    var pLeftVal = height[pLeft];
    var pRightVal = height[pRight];

    if(pLeftVal > pRightVal) {
      maxArea = Math.max( len * pRightVal, maxArea );
      pRight --;
    }
    else {
      maxArea = Math.max( len * pLeftVal, maxArea );
      pLeft ++;
    }
    len --;
  }    
  return maxArea;
};



var height = [1,8,6,2,5,4,8,3,7];
console.log( maxArea(height) );