End Course Capstone Project - Module 2

00_End Course Capstone Project.md

End Course Capstone Project (Module 2)

Capstone Project Submission Instructions

1. Login/Sign Up to your GitHub account.
2. Fork this Gist from the Top-Right corner.
3. Edit your Gist and paste/write the code solutions inside the respective functions.
4. Share your Gist link in the submission form as per the instructions given.

- Do not make any changes in the first 3 lines

End.Course.Capstone.Project.Submission.Video.mp4

01_cbf-01_isPowerOfTwo.js

module.exports = { isPowerOfTwo };

function isPowerOfTwo(n) {
    
    return n > 0 && (n & (n - 1)) === 0;
}

02_cbf-02_minAddToMakeValid.js

module.exports = { minAddToMakeValid };


/* 
var minAddToMakeValid = function(s) {
    let open = 0, close = 0;
    
    for(let c of s) {
        if(c === '(') open++;
        else if(open) close++;
        else open--;
    }
    return open + close;
};
*/

var minAddToMakeValid = function(s) { // "(()" , "())"
    let open = 0, close = 0;
    
    for(let c of s) {
        if(c === '(') open++;
        else if(open) open--;
        else close++;
    }
    return open + close;
};

03_cbf-03_callPoints.js

module.exports = { callPoints };

function callPoints(operations) {
    for (let i = 0; i < operations.length; i++) {
        if (operations[i] === "+") {
            let sum = operations[i - 2] + operations[i - 1];
            operations[i] = sum;
        } else if (operations[i] === "D") {
            let newD = operations[i - 1] * 2;
            operations[i] = newD;
        } else if (operations[i] === "C") {
            operations.splice(i - 1, 2);
            i = i - 2;
        } else {
            var integer = +operations[i];
            operations[i] = integer;
        }
    }

    // to calculate the totalSum only
    let totalSum = 0;
    for (let i = 0; i < operations.length; i++) {
        totalSum += operations[i];
    }

    return totalSum;
}

04_cbf-04_sortPeople.js

module.exports = { sortPeople };

/*
var sortPeople = function(names, heights) {
    let length = heights.length();
    let map = new Map();
    for(let i=0; i<=length; i++){
        map.set(heights[i], names[i]);
    }
    heights.sort((a,b) => b-a);
    let res = [];
    for(let height of heights){
        res.push(map.get(height));
    }
    return res;
};
*/

function sortPeople(names, heights) {
    let length = heights.length;
    let map = new Map();
    for(let i=0; i < length; i++){
        map.set(heights[i], names[i]);
    }
    heights.sort((a,b) => b-a);
    let res = [];
    for(let height of heights){
        res.push(map.get(height));
    }
    return res;
};

05_cbf-05_findErrorNums.js

module.exports = { findErrorNums };

function findErrorNums(nums) {
    const hashmap = new Map();
    const output = [];
    let maxValue = 0;

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (hashmap.has(num)) output.push(num);
        hashmap.set(num, i);
        maxValue = Math.max(maxValue, num);
    }

    for (let i = 1; i <= maxValue + 1; i++) {
        if (!hashmap.has(i)) {
            output.push(i);
            break;
        }
    } 
    
    return output;
};

06_ip-01_isHappy.js

module.exports = { isHappy };

function isHappy(n) {
   const calculateSumOfSquares = (num, visited) => {
     if(num === 1){
        return true
     }

     if(visited.has(num)){
        return false;
     }

     visited.add(num)

     let sum = 0;
     while(num > 0){
        let digit = num % 10;
        sum += digit * digit;
        num = Math.floor(num / 10);
     }

     return calculateSumOfSquares(sum, visited)
   }

   const visited = new Set();
   return calculateSumOfSquares(n, visited)
}

07_ip-02_isPalindrome.js

module.exports = { isPalindrome };

/*
function isPalindrome(n) {
    let dupNum = 0;
    let backN = n;
    
    while (n) {
        let rem = n % 10;
        dupNum = dupNum * 10 + rem;
        n = Math.floor(n / 10);
    }
    
    if (dupNum === backN) {
        return true;
    }
    
    return false;
}

Rewrite the above given JavaScript code using the 2-pointer approach.
*/

function isPalindrome(n) {
   let numString = n.toString();

   let i = 0;
   let j = numString.length - 1;

   while(i <= j){ // 
    if(numString[i] !== numString[j]){
        return false;
    }
    j--;
    i++;
   }

   return true;
}

08_ip-03_fairCandySwap.js

module.exports = { fairCandySwap };

function fairCandySwap(aliceSizes, bobSizes) {
    let sumAlice = aliceSizes.reduce((acc, size) => acc + size, 0);
    let sumBob = bobSizes.reduce((acc, size) => acc + size, 0);

    let targetSum = (sumAlice + sumBob) / 2;

    // Create a HashMap (using an object) to store the elements of bobSizes for quick lookup
    let bobSizesHashMap = {};
    bobSizes.forEach(size => bobSizesHashMap[size] = true);

    for (let i = 0; i < aliceSizes.length; i++) {
        let a = aliceSizes[i];
        let b = targetSum - (sumAlice - a);

        if (bobSizesHashMap[b]) {
            return [a, b];
        }
    }
};

09_ip-04_nextGreatestLetter.js

module.exports = { nextGreatestLetter };

function nextGreatestLetter(letters, target) {
    // binary search

    let ans;
    let check = false;

    let l = 0;
    let size = letters.length;
    let h = size - 1;

    while (l <= h) {
        let mid = h - Math.floor((h - l) / 2);

        if (letters[mid] <= target) {
            l = mid + 1;
        } else {
            let currAns = letters[mid];
            check = true;
            if (mid >= 0) {
                h = mid - 1;
            }
            ans = currAns;
        }
    }
    
    if (!check) {
        return letters[0];
    }
    
    return ans;
}

10_ip-05_searchRange.js

module.exports = { searchRange };

function searchRange(nums, target) {
     let ans = [-1, -1];

    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            ans[0] = mid;
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    left = 0;
    right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            ans[1] = mid;
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return ans;
};

11_lb-01_findPeakElement.js

module.exports = { findPeakElement };
/*
In the mysterious land of numbers, there lies a hidden peak, an element that stands tall and proud, surpassing its neighboring digits.
The inhabitants of this land,
represented by a 0-indexed integer array called "nums," seek to uncover this majestic peak and bring forth its enigma to light.
They have tasked you with the challenge.
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, along with the findPeakElement function, your goal is to find a peak element and return its index. If the array contains multiple peaks, you can return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -Infinity. In other words, an element is always considered to be strictly
greater than a neighbor that is outside the array.
You are required to implement the findPeakElement function using an algorithm that runs in O(log n) time.
*/
function findPeakElement(nums) { // [1,2,1,4,5,4]
     let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);

        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

   
    return left;
}

12_lb-02_sortColors.js

module.exports = { sortColors };

function sortColors(nums) {
const merge = (left, right) => {
    let mergedArr = []
    let leftIndex = 0;
    let rightIndex = 0;

    while(leftIndex < left.length && rightIndex < right.length){
        if(left[leftIndex] < right[rightIndex]){
        mergedArr.push(left[leftIndex]);
        leftIndex++;
        }else{
            mergedArr.push(right[rightIndex]);
            rightIndex++;
        }
    }

        mergedArr.push(...left.slice(leftIndex));
    


        mergedArr.push(...right.slice(rightIndex));
    

    return mergedArr
}

   if(nums.length <= 1){
        return nums
   }

   
   let mid = Math.floor(nums.length/2)

   const leftArr = nums.slice(0, mid);
   const rightArr = nums.slice(mid);

   const sortedLeft = sortColors(leftArr);
   const sortedRight = sortColors(rightArr);

   return merge(sortedLeft, sortedRight)



}

13_lb-03_maxCount.js

module.exports = { maxCount };

function maxCount(nums) { // [-3,-2,-1,0,0,1,2]
   let posCount = 0;
   let negCount = 0;

   for(let i = 0; i < nums.length; i++){
    if(nums[i] > 0){
        posCount++;
    }else if(nums[i] < 0){
        negCount++;
    }
   }

   let max = Math.max(posCount, negCount);
   return max;
}

14_lb-04_minimumSum.js

module.exports = { minimumSum };

function minimumSum(num) {
  const digits = num.toString().split("").map(Number);

   digits.sort((a, b) => a - b);
   let firstSmallest = digits.shift();
   let secondSmallest = digits.shift();

   let num1 = parseInt(firstSmallest.toString() + digits[0].toString())
   let num2 = parseInt(secondSmallest.toString() + digits[1].toString())

   return num1 + num2
}

15_lb-05_transitionPoint.js

module.exports = { transitionPoint };

function transitionPoint(arr) {
   let left = 0;
  let right = arr.length - 1;

  while(left < right){
    const mid = Math.floor((left + right) / 2);

    if(arr[mid] === 1){
        return mid;
    }else if(arr[mid] < 1){
        left = mid + 1;
    }else{
        right = mid -1;
    }
  }

  return -1
}

16_tvo-01_missingNumber.js

// Traditional Approach

var missingNumber = function(arr) {
    let n=arr.length;
     let hashSet = new Set();
 
  // Add all elements of array to hashset
  for (let i = 0; i < n ; i++) {
    hashSet.add(arr[i]);
  }
 
  // Check each integer from 1 to n
  for (let i = 1; i <= n; i++) {
    // If integer is not in hashset, it is the missing integer
    if (!hashSet.has(i)) {
      return i;
    }
  }
 
  // If no integer is missing, return n+1
  return 0;
};

// Optimized Approach

var missingNumber = function(arr) {
    let n = arr.length;

    for (let i = 0; i < n; i++) {
        while (arr[i] > 0 && arr[i] <= n && arr[arr[i] - 1] !== arr[i]) {
            [arr[arr[i] - 1], arr[i]] = [arr[i], arr[arr[i] - 1]];
        }
    }

    for (let i = 0; i < n; i++) {
        if (arr[i] !== i + 1) {
            return i + 1;
        }
    }
    return n + 1;
};


// Provide your comparison here.
/*1) The optimized approach is better because it achieves the same goal with constant space complexity
i.e O(1) as compared to the first approach which was taking extra space because of hash set.
 2) The Optimized approach also performs fewer iterations over the array, making it more efficient.
*/

17_tvo-02_duplicateCheck.js

// Traditional Approach

class Solution{
    duplicateCheck(str){
        //code here
        let temp = ''+ str[0];
        for(let i=0;i<str.length;i++){
            if(temp.indexOf(str[i]) == -1){
                temp = temp+str[i];
            }
        }
        return temp;
    }
}

// Optimized Approach

class Solution{
    duplicateCheck(str){
        const p=new Set(str);
        const t=[...p];
        return t.join("");
    }
}

// Provide your comparison here.
/* 
 1) The Time complexity for the optimized approach would be O(n), as creating an array from set
 involves iterating through the array once. Whereas in the traditional approach, the time
 complexity would be O(n^2), becuase for each character it may need to traverse the temp string.
 2) So with the optimized approach, we are doing efficient traversal, making the code run faster.
*/

18_tvo-03_chunkArrayInGroups.js

// Traditional Approach

function chunkArrayInGroups(arr, size) {
  let temp = [];
  const result = [];

  for (let a = 0; a < arr.length; a++) {
    if (a % size !== size - 1) temp.push(arr[a]);
    else {
      temp.push(arr[a]);
      result.push(temp);
      temp = [];
    }
  }

  if (temp.length !== 0) result.push(temp);
  return result;
}

// Optimized Approach

function chunkArrayInGroups(arr, size) {
  // Break it up.
  const newArr = [];
  let i = 0;

  while (i < arr.length) {
    newArr.push(arr.slice(i, i + size));
    i += size;
  }
  return newArr;
}



// Provide your comparison here.
/*
1) The optimized approach is concise and easy to understand, since it doesn't have a lot of
conditional statements, and also we are not using any temp storage.
2) Both the approaches offer similar time and space complexity which is O(n), but the optimized 
approach uses slice method , which is already optimized by the javascript engine, so it performs
more efficiently than the traditional one.
Overall, optimized approach is less complex and more efficient
*/

19_tvo-04_enchantedArrayShuffling.js

// Traditional Approach

function enchantedArrayShuffling(originalArray) {
  const sortedArray = [...originalArray].sort((a, b) => a - b);
  const shuffledArray = [];

  let left = 0;
  let right = sortedArray.length - 1;

  while (left <= right) {
    if (left === right) {
      shuffledArray.push(sortedArray[left]);
    } else {
      shuffledArray.push(sortedArray[left]);
      shuffledArray.push(sortedArray[right]);
    }

    left++;
    right--;
  }

  return shuffledArray;
}

// Optimized Approach

function enchantedArrayShuffling(originalArray) {
  const sortedArray = [...originalArray].sort((a, b) => a - b);
  const shuffledArray = [];

  let left = 0;
  let right = sortedArray.length - 1;

  while (left < right) {
    shuffledArray.push(sortedArray[left++]);
    shuffledArray.push(sortedArray[right--]);
  }

  if (left === right) {
    shuffledArray.push(sortedArray[left]);
  }

  return shuffledArray;
}



// Provide your comparison here.
/* both the traditional and optimized approaches have a time complexity dominated by 
the sorting operation, which is O(n log n) in the worst case. However, the shuffling 
process in the optimized approach has a linear time complexity of O(n) due to its single pass
through the sorted array. In terms of space complexity, both approaches require O(n) 
 additional space to store intermediate arrays.
*/

20_tvo-05_findPairWithSum.js

// Traditional Approach

function findPairWithSum(array, targetSum) {
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] + array[j] === targetSum) {
        return [array[i], array[j]];
      }
    }
  }
  return [];
}

// Optimized Approach

function findPairWithSum(array, targetSum) {
  const numMap = {};

  for (let i = 0; i < array.length; i++) {
    const difference = targetSum - array[i];
    if (numMap[array[i]]) {
      return [difference, array[i]];
    }
    numMap[difference] = true;
  }

  return [];
}



// Provide your comparison here.
/*
1) The traditional approach has a time complexity of O(n^2) because of nested for loops.
whereas the optimal approach has a time complexity of O(n), because we are iterating over an element 
only once. Although to obtain O(n) time complexity we have made a tradeoff with space, the space
complexity of traditional approach is O(1), and for the optimal it is O(n) as we are using extra
storage. Overall the optimized approach is more efficient.

*/

21_bws-01_maxBitwise.js

// Worst Case

function worstmaxBitwise(arr) {
    let maxAnd = 0;

    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            let currentAnd = arr[i] & arr[j];
            maxAnd = Math.max(maxAnd, currentAnd);
        }
    }

    return maxAnd;
}

// Best Case

function bestmaxBitwise(arr) {
    let maxAnd = 0;

    for (let bit = 31; bit >= 0; bit--) {
        let mask = 1 << bit;
        let possibleMaxAnd = maxAnd | mask;

        let allNumbers = arr.every(num => (num & possibleMaxAnd) !== 0);

        if (allNumbers) {
            maxAnd = possibleMaxAnd;
        }
    }

    return maxAnd;
}

22_bws-02_flipAndInvertImage.js

// Worst Case

function worstflipAndInvertImage(image) {
    const reverse = (arr) => {
      let i = 0;
      let j = arr.length -1;

      while(i < j){
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
      }

      return arr;
    }

    for(let i = 0; i < image.length; i++){
        image[i] = reverse(image[i]);
    };

    for(let i = 0; i < image.length; i++){
        for(let j = 0; j < image[i].length; j++){
            if(image[i][j] === 0){
                image[i][j] = 1;
            }else{
                image[i][j] = 0;
            }
        }
    }

    return image;
}

// Best Case

function bestflipAndInvertImage(image) {
    const numRows = image.length;
    const numCols = image[0].length;

    for (let i = 0; i < numRows; i++) {
        // Only iterate through half of the columns
        for (let j = 0; j < Math.ceil(numCols / 2); j++) {
            // Swap values across the middle column
            const temp = image[i][j];
            image[i][j] = image[i][numCols - 1 - j] === 0 ? 1 : 0;  // Flip without XOR
            image[i][numCols - 1 - j] = temp === 0 ? 1 : 0;
        }
    }

    return image;
}

23_bws-03_asteroidCollision.js

// Worst Case

function worstasteroidCollision(arr) {
   const stack = [];
  for(let i = 0; i < arr.length; i++){
    if(stack.length < 1 || arr[i] >= 0){
        stack.push(arr[i]);
    }else{
        while(true){
            let peek = stack[stack.length -1];
            if(peek < 0){
              stack.push(arr[i]);
              break;
            }else if(peek === Math.abs(arr[i])){
                stack.pop();
                break;
            }else if(peek > Math.abs(arr[i])){
              break;
            }else{
                stack.pop();
                if(stack.length < 1){
                    stack.push(arr[i]);
                    break;
                }
            }
        }
    }
  }

  return stack;
}

// Best Case

function bestasteroidCollision(arr) {
     const stack = [];

    for (let i = 0; i < arr.length; i++) {
        let current = arr[i];

        // Check if the stack is not empty and the current asteroid is moving to the left
        while (stack.length > 0 && stack[stack.length - 1] > 0 && stack[stack.length - 1] < Math.abs(current)) {
            stack.pop(); // Destroy the right-moving asteroid on the stack
        }

        if (stack.length === 0 || stack[stack.length - 1] < 0) {
            stack.push(current); // Push the left-moving asteroid
        } else if (stack[stack.length - 1] === Math.abs(current)) {
            stack.pop(); // Destroy both asteroids
        }
        // If the stack top is a positive asteroid greater than the current's absolute value, do nothing (current asteroid is destroyed)
    }

    return stack;
}

24_bws-04_findRelativeRanks.js

// Worst Case

function worstfindRelativeRanks(score) {
   let sortedScore = score.slice().sort((a, b) => b- a);
   let first = sortedScore[0];
   let second = sortedScore[1];
   let third = sortedScore[2];

   let result = [];

   for(let i = 0; i < score.length; i++){
     if(score[i] === first){
        result.push("Gold Medal")
     }else if(score[i] === second){
        result.push("Silver Medal")
     }else if(score[i] === third){
        result.push("Bronze Medal")
     }else{
        let temp = sortedScore.indexOf(score[i]) + 1;
        let stringTemp = temp.toString()
        result.push(stringTemp);
     }
   }

   
   return result;
}

// Best Case

function bestfindRelativeRanks(score) {
  let result = []

  if(score.length > 2){
    for(let i = 0; i < 3; i++){
        if(result.length === 0){
            result.push("Gold Medal")
        }else if(result.length === 1){
            result.push("Silver Medal")
        }else{
            result.push("Bronze Medal")
        }
    }
  }

  for(let i = 3; i < score.length; i++){
    let num = i + 1;
    result.push(num.toString())
  }

  return result
}

25_bws-04_maxHex.js

// Worst Case

function worstMaxHex(arr) {
    let maxXOR = 0;

    for (let i = 0; i < hexArray.length; i++) {
        for (let j = i + 1; j < hexArray.length; j++) {
            const num1 = parseInt(hexArray[i], 16);
            const num2 = parseInt(hexArray[j], 16);
            const currentXOR = num1 ^ num2;
            maxXOR = Math.max(maxXOR, currentXOR);
        }
    }

    return maxXOR.toString(16);
}

// Best Case

function bestMaxHex(arr) {
    // Write your code inside this function only.


}