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]