arrays1.js

/**
 * Return true if palindrom
 * place i = 0; j = arr1.length - 1
 * while i < j end of loop return TRUE
 * if (arr1[i] != arr1[j]) {
 *   return false
 *}
 * i++;
 * j--;
 * Time Complexity: O(N)
 * Space Complexity: O(1)
 */

const checkIfPalindrome (arr1) => {
  let i = 0;
  let j = arr1.length - 1;
  while (i < j) {
    if (arr1[i] != arr1[j]) {
      return false;
    }
    i++;
    j--;
  }
  return true;
}


/**
 * Return pair of numbers that add up to the target in a sorted array
 * nums = [1,2,3,4]
 * target = 5
 * return [1,4], [2,3]
 *
 * place i at index 0 & j at index + 1
 * two loops first pts loop until i < len(nums)-1
 * second loop start at j = i + 1 until len(nums)-1
 * check if value at i + j === target store
 * the index pair
 * else increment j
 * at end of 1st loop return the pairs
 * Time complexity O(n^2)
 * Space complexity O(1)
 *
 */
TBD
/**
 * Return a new array that combine two sorted arrays arr1 and arr2
 * arr1 = [1,4,7,20]
 * arr2 = [2,3,5,6]
 * return [1,2,3,4,5,6,7,20]
 *
 * set i = 0, j = 0 for arr1 and arr2
 * in a while loop compare length arr1[i] and arr2[j]
 * if arr1[i] < arr2[j] push arr1[i]
 * then increment i compare arr1[i] < arr2[j]
 * then push arr2[j] now increment j
 * at end of while loop push the rest of the arr1 and arr2
 * for remaing left out array
  // while (i < arr1.length) {
  //   newArr.push(arr1[i]);
  //   i++
  // }
 * repeat the same  for arr 2
 * Time & Space complexity O(n)
 */

const combinArrs = (arr1, arr2) => {
  let i = 0, j = 0;
  let newArr = [];
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      newArr.push(arr1[i]);
      i++;
    }
    else {
      newArr.push(arr2[j]);
      j++;
    }
  }
  while (i < arr1.length) {
    newArr.push(arr1[i]);
    i++
  }
  while (j < arr2.length) {
    newArr.push(arr1[j]);
    j++
  }
}

const arr1 = [1,4,7,20]
const arr2 = [2,3,5,6]
combinArrs(arr1, arr2)

/*
Return subsequence of a string
check if s is subsequenc of t
s = "abc"
t = "ahcgdb"

s = "aec"
t = "abcde"

- set i = 0, j = 0
while i < s.length
  if (s[i] === t[j])) {
    i++
    j++
  }
  if (s[i] != t[j]) {
    j++
  }
  if (j === t.length) return false
return true
*/

const isSubsequence = (s, t) => {
  let i = 0, j = 0;
  while (i < s.length && j < t.length) {
    if (s[i] === t[j]) {
      i++;
    }
      j++;
  }
  return i === s.length;
}

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */

/*
* Reverse a string s. Do not return anything, modify s in-place instead.
Input: s = ["h","e","l","l","o"]
Output: s = ["o","l","l","e","h"]

Input: s = ["a", "p", "p", "l", "e", "s"]
Output: s = ["s", "e", "l", "p", "p", "a"]

- i = 0
- j = len(s) - 1
- use while loop so that i & j don't crossover i < j
- swap the variables then i++ & j--
- Time Complexity: O(N)
- Space Complexity: O(1)
*/
var reverseString = function(s) {
    i = 0
    j = s.length - 1
    while (i< j) {
        let temp = s[i];
        [s[i], s[j]] = [s[j], s[i]];
        i++;
        j--;
    }   
};

/**
 * @param {number[]} nums
 * @return {number[]}
 Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Square & sort
- start the loop in reverse
- then place two ptrs on each end 
- square & compare move the greater ele
- to new array using newArray[i]
- if move is from leftSq then increment start
- if move is from rightSq then decrement end
- Time complexity: O(N)
- Space complexity: O(N)

 */
var sortedSquares = function(nums) {
    const arrLen = nums.length
    const result = new Array(arrLen);
    let start = 0
    let end = arrLen - 1 
    for (i = arrLen - 1; i >= 0; i--) {
        let leftSq = nums[start] ** 2
        let rightSq = nums[end] ** 2
        if (leftSq > rightSq) {
            result[i] = leftSq;
            start++;
        }
        else {
            result[i] = rightSq;
            end--;
        }
    }
    return result; 
};



/*
Length of longest subarray whose sum is less
than or equal to k.

nums = [3,1,2,3,4,5]
k = 2
o/p: [2]

nums = [3, 1, 2, 7, 4, 2, 1, 1, 5] 
k = 8
o/p: [2,1,1,5]

Sliding Window 
start by initalizing 
l = 0
i = 0
maxLen = 0
curr = 0 // to keep track of the var
use a for loop to go thru the array
curr += nums[i]
r++
use a while loop to check if curr is 
greater than k
enter the while loop:
curr -= nums[i]
l++
at end of while loop
maxLen = Math.max(maxLen, r-l+1)

at end of for loop return maxLen

Time Complexity: O(N)
Space Complexity: O(1)

*/

const longestSubarray = (nums, k) => {
  let l = 0, maxLen = 0, curr = 0;
  for (let r = 0; r <= nums.length; r++) {
    curr += nums[r];
    while(curr > k){
      curr -= nums[r];
      l++
    }
    maxLen = Math.max(maxLen, r-l+1);
  }
  
  console.log('maxLen', maxLen);
}

longestSubarray([3, 1, 2, 7, 4, 2, 1, 1, 5], 8)




/*
return the number of subarrays where the product of all 
the elements in the subarray is strictly less than k.

nums = [10, 5, 2, 6], k = 100
o/p: 8

[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]

start by initalizing 
l = 0
i = 0
maxLen = 0
curr = 0 // to keep track of the var
use a for loop to go thru the array
curr *= nums[i]
r++
use a while loop to check if curr is 
greater than k
enter the while loop:
curr /= nums[i]
l++
at end of while loop
maxLen +=  r-l+1

at end of for loop return maxLen

Time Complexity: O(N)
Space Complexity: O(1)

*/

const subarrayProduct = (nums, k) => {
  let l = 0, maxLen = 0, curr = 0;
  for (int i = 0; i < nums.length; i++) {
    curr *= nums[i];
    while (curr > k){
      curr /= nums[i];
      l++;
    }
    maxLen += i - l + 1
  }
  return maxLen;
}



/*
find th sum of the subarray with the largest sum whose len is k
nums = [3, -1, 4, 12, -8, 5, 6]
k = 4
18, 7, 12, 1
o/p: 18

using a for loop find the sum of first k
then in another for loop 
remove ele from left & add to the right
 curr += nums[k] - nums[i-k];
then update max len
Time Complexity: O(N)
Space Complexity: O(1)
*/

const findBestSubarray = (nums, k) => {
  let curr = 0;
  for (let i = 0; i < nums.length; i++ ){
    curr += nums[i];
  }
  let ans = curr;
  for (let i = k; i<  nums.length ; i++){
    curr += nums[k] - nums[i-k];
    ans = Math.max(ans, curr)
  }
  return ans
}

/*
Find a contiguous subarray whose length is equal to k 
that has the maximum average value
nums = [1,12,-5,-6,50,3], k = 4
o/p = 12.75000

fixed sliding window

- using a for loop find the avg sum up until len k
- store ans = curr
- then in a 2nd for loop (i = k) remove ele from left
- curr = curr*4
- add to the right curr += nums[k] - nums[i-k];
- curr / 4
- get the ans = max(ans, curr)
or retun ans/k to return avg.
Time Complexity: O(N)
Space Complexity: O(1)
*/

const findMaxAverage = (nums, k) => {
  let curr = 0;
  for (let i = 0; i < k; i++){
    curr += nums[i];
  }
  let ans = curr;
  for (i = k; i < nums.length; i++){
    curr += nums[k] - nums[i-k];
    ans = Math.max(ans, curr);
  }
   console.log('ans', ans/k)
}

findMaxAverage([1,12,-5,-6,50,3], 4)

/*
return a boolean array that represents the answer to 
each query.
A query is true if the sum of the subarray from x to y
is less than limit, or false otherwise
nums = [1, 6, 3, 2, 7, 2]
queries = [[0, 3], [2, 5], [2, 4]]
limit = 13
o/p: [true, false, true]
[12, 14, 12]

- find the prefix sum = nums[i]+ prefix[prefix.length - 1])
- find sum of subarray curr = prefix[j] - prefix[i] + nums[i] 
- compare curr with limit & return boolean array 

Time & Space Complexity:O(N)
*/

const answerQ = (nums, queries, limit) => {
  let prefix = [nums[0]]
  for (let i = 1; i < nums.length; i++){
    prefix.push(nums[i]+ prefix[prefix.length - 1]);
  }
  console.log('prefix', prefix)
  let ans = []
  for (const [x, y ]of queries){
    let curr = prefix[y] - prefix[x] + nums[x];
    ans.push(curr < limit)
  }
  console.log('ans', ans)
}

answerQ([1, 6, 3, 2, 7, 2], [[0, 3], [2, 5], [2, 4]], 13)

/*
number of ways to split the array into two parts so that the 
first section has a sum greater than or equal to the sum of the second section.
nums = [10,4,-8,7]
prefix = [10,14,6,13]
o/p = 3

[10| 4,-8,7]  13 - 10  = -3 < 10 valid
[10,4,|-8,7] 13 - 14 = -1 < 14 valid
[10,4,-8,|7] 13 - 6 = 7 > 6 invalid

- find the prefix sum = nums[i]+ prefix[prefix.length - 1])
- then find left section = prefix[i]
- then find right section = prefix[n-1] - prefix[i]

Time & Space Complexity:O(N)
*/


const splitArray = (nums) => {
  const n = nums.length;
  let prefix = [nums[0]];
  for (let i = 1; i < n; i++){
    prefix.push(nums[i]+ prefix[prefix.length - 1]);
  }
  let ans = 0;
  for (let i = 0; i < n - 1; i++){
    let leftSection = prefix[i];
    let rightSection = prefix[n - 1] - prefix[i];
    if (leftSection > rightSection) {
      ans++;
    }
  }
  return ans;
}


/*
 K Radius Subarray Averages
 - given nums & k
 - n = 0, avgs = [-1], prefix=[]
 - if k is 0, we have to find the avg. of
 only 1 number at each index, so return nums
 - if 2*k+1 > n, find avg. of more than n, return
 avgs array
 - Generate prefix array of nums
 - Iterate on those indices which will have at least
 k elements on left & right sides, calc. sum of 
 the req. sub-array using prefix array
 prefix[rBound+1]-prefix[lBound], store the avg. by
 dividing the sum by windowSize in avgs array
 
 Time & Space Complexity:O(N)
 
*/


const getAvgs = (nums, k) => {
  // if k is 0, return nums
  if (k === 0){
    return nums;
  }
  const windowSize = 2 * k + 1
  const n = nums.length;
  const avgs = new Array(n).fill(-1);
  
  // if 2*k+1 > n, find avg. of more than n, return avgs
  
  if (windowSize > n){
    return avgs;
  }

  let prefix = [nums[0]];
  for (let i = 1; i < n; i++){
    prefix.push(nums[i]+ prefix[prefix.length - 1]);
  }
  
  // We iterate only on those indices which have at least 'k' elements in their left and right.
  // i.e. indices from 'k' to 'n - k'
  
  for (let i=k;i<(n-k);++i){
    const lBound = i - k, rBound = i + k;
    const subArraySum = prefix[rBound+1]-prefix[lBound]
    const avg = Math.floor(subArraySum/windowSize);
    avgs[i] = avg;
  }
  return avgs;
}
/*
Revers Words in a String |||

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Input: s = "Mr Ding"
Output: "rM gniD"

- convert string into array of words
- [ 'Mr', 'Ding' ] => s.split('')
- in a for loop get each word
- get the length of the word
- set 2 ptrs i = 0 & j = word.length - 1
- convert word into array of word
- in a while loop (i < j), swap i & j
- [s[i], s[j]] = [s[j], s[i]];
- i++ & j-- as required
- convert word into string
- convert array of words into string
- Splitting the input string s into an array of words using split(' '): 
- This operation has a time complexity of O(n), where n is the length of the input string.
- Iterating over each word in the array and reversing it: This involves iterating over 
- each character in each word once, so it has a time complexity of O(m)
- Time complexity: O(n + m) = O(N)
- Space complexity: O(N)

*/

const reverseWords = (s) => {
  let reverseStr = []
  s = s.split(' ')
  s.forEach(word => {
    let n = word.length;
    let i = 0;
    let j = n - 1;
    word = word.split('');
    while(i < j){
      [word[i], word[j]] = [word[j], word[i]];
      i++;
      j--;
    }
    reverseStr.push(word.join(''))
  })
  reverseStr = reverseStr.join(' ');
  console.log('reverseStr', reverseStr)
  return reverseStr
}

s = "Let's take LeetCode contest"
reverseWords(s)

/*
Reverse only letter

Input: s = "ab-cd"
Output: "ba-dc"

Input: s = "Test1ng-Leet=code-Q!"
Output: "tseT1gn-teeL=edoc-Q!"
- Place 2 ptrs at i = 0; j = s.length - 1
- Use isAlpha helper function
- return /^[a-zA-Z]+$/.test(str)
- in a while loop i < j
- if i & j both isAlpha then swap
- if either i or j not isAlpha then
either i++ or j--
- at end of loop, return s
- Time complexity: O(N)
- Space complexity: O(1)
*/


const reverseOnlyLetters = (s) => {
  s = s.split('')
  let i = 0
  let j = s.length - 1
  while(i < j){
    if(isAlpha(s[i]) && isAlpha(s[j])) {
      [s[i], s[j]] = [s[j], s[i]];
      i++;
      j--;
    }
    if(!isAlpha(s[i])){
      i++;
    }
    if(!isAlpha(s[j])){
      j--;
    }
  }
  console.log('sss', s.join(''))
  return s.join('')
};


const isAlpha = (str) => {
  return /^[a-zA-Z]+$/.test(str)
}

reverseOnlyLetters("Test1ng-Leet=code-Q!")

/*
Input: nums1 = [1,2,3], nums2 = [2,4]
Output: 2
Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5]
Output: min(2 & 3) = 2

- place a pointer at i & j = 0 for nums1 & nums2
- in a for loop iterate i & then in another loop
iterate j, if nums1[i] === nums[j], 
- then push into result []



*/
const getCommon = (nums1, nums2) => {
  let result = []
  for(i=0; i<nums1.length-1; i++){
    for(j=0; j<nums2.length-1; j++){
      if (nums1[i]===nums2[j]){
        result.push(nums1[i])
      }
  }
};
  console.log('res', Math.min(...result))
  return Math.min(...result)
}
getCommon([1,2,3,6], [2,3,4,5])

/*
move all 0s to the end of it while maintaining
the relative order of the non-zero elements

nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

nums = [0]
Output: [0]

- Place i ptr. at nearest 0 then place second ptr j
at next element
- if j is non zero then swap with i, j++
- if j is zero, then j++
- if i reaches end of length, then set i to next 0

*/

const moveZeroes = (nums) => {
    let i = 0;
    for (let j = 1; j < nums.length; j++){
        if(nums[j]!== 0){
            let tmp = nums[j];
            nums[j] = nums[i];
            nums[i] = tmp;
            i++
        }
    }
    console.log(nums)
};

moveZeroes([0,1,0,3,12])

/**
 * reverse prefix of word
 * Input: word = "abcdefd", ch = "d"
 * Output: "dcbaefd"
 * Input: word = "xyxzxe", ch = "z"
 * Output: "zxyxxe"
 * find the occurrence of ch in word
 * then reverse from ch index until 0
 * in a loop find the occurence of ch
 * & return the index
 * place two ptrs at i = 0 & j = index of ch 
 * then swap the pointers in a while loop i < j
 *  word = word.slice(0,i) + word[j] + word.slice(i+1,j) + word[i] + word.slice(j+1)
 * i++ & j--
 * Time complexity: O(N)
 * Space complexity: O(1)
 */
const reversePrefix = (word, ch) => {
    let firstIndex = -1;
    for(let k = 0; k <= word.length - 1; k++) {
        if (word[k] === ch) {
            firstIndex = k;
            break; // exit loop on first occurence
        }
    }
    let i = 0;
    let j = firstIndex;
    while(i < j) {
        if (word[i] !== word[j]) {
            word = word.slice(0,i) + word[j] + word.slice(i+1,j) + word[i] + word.slice(j+1);
        }
        i++;
        j--;
    }
};

reversePrefix("abcdefd", "d")