Algorithms study

Longest common prefix

const longestCommonPrefix = (strs: string[]): string => {
  return strs.reduce((acc, current) => {
    while (current.slice(0, acc.length) !== acc) {
      acc = acc.slice(0, acc.length - 1);
    }
    return acc;
  }, strs[0])
};

Merge 2 sorted linked lists

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

const mergeTwoLists = (list1: ListNode | null, list2: ListNode | null): ListNode | null => {
    const head: ListNode = new ListNode();
    let curr = head;

    while (list1 && list2) {
        if (list1.val < list2.val) {
            curr.next = list1;
            list1 = list1.next;
        } else {
            curr.next = list2;
            list2 = list2.next;
        }

        curr = curr.next;
    }
    
    curr.next = list1 || list2;

    return head.next;
};

Palindrome number

const isPalindrome = (x: number): boolean => {
    let num = String(x);
    let reversedNum = "";

    if (x < 0) { 
        return false; 
    }

    for (let i = num.length - 1; i >= 0; i--) {
        reversedNum += num[i];

        if (num.slice(0, reversedNum.length) !== reversedNum) {
            return false;
        }
    }

    return true;
};

// without converting into string
const isPalindrome = (x: number): boolean => {
    let num = x;

     if (num < 0 || (num && num % 10 === 0)) { 
        return false; 
    }
    
    const digits = [];
    
    while (num) {
        digits.push(num % 10);
        num = Math.floor(num / 10);
    }
    
    for (let i = 0, j = digits.length - 1; i < j; i++, j--) {
        if (digits[i] !== digits[j]) {
            return false;
        }
    }
    
    return true;
};

Roman to integer

const romanToInt = (s: string): number => {
  const romanHash = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
  };

  let integer = 0;

  for (let i = 0; i < s.length;) {
    const currentNumber = romanHash[s[i]];
    const nextNumber = romanHash[s[i + 1]];
    const isSubtraction = currentNumber < nextNumber;

    if (isSubtraction) {
      integer += nextNumber - currentNumber;
      i += 2;
    } else {
      integer += currentNumber;
      i += 1;
    }
  }

  return integer;
};

Sort people

const sortPeople = (names: string[], heights: number[]): string[] => {
  const sortedNames = [...names];
  const sortedHeights = [...heights];

  for(let i = 0; i < sortedHeights.length; i++) {
    for(let j = i+1; j < sortedHeights.length; j++) {
      if(sortedHeights[i] < sortedHeights[j]){
        const swapName = sortedNames[i];
        sortedNames[i] = sortedNames[j];
        sortedNames[j] = swapName;

        const swapHeight = sortedHeights[i];
        sortedHeights[i] = sortedHeights[j];
        sortedHeights[j] = swapHeight;
      }
    }
  }

  return sortedNames;
};

Two Sum

const twoSum = (nums: number[], target: number): number[] => {
  for (let i = 0; i < nums.length; i++) {
    const firstNumber = nums[i];

    if (target >= 0 && firstNumber <= target || target < 0 && firstNumber >= target) {
      for (let j = 0; j < nums.length; j++) {
        const secondNumber = nums[j]

        if (firstNumber + secondNumber === target  && i !== j) {
          return [i, j]
        }
      }
    }
  }
};

Valid parentheses

const isValid = (s: string): boolean => {
  const matchBrackets = {
    "(": ")",
    "[": "]",
    "{": "}",
  }

  const temp = [];
  const openBrackets = Object.keys(matchBrackets);

  for (let i = 0; i < s.length; i++) {
    const bracket = s[i];
    if (openBrackets.includes(bracket)) {
      temp.push(bracket);
    }

    else if (matchBrackets[temp.pop()] !== bracket) {
      return false;
    }
  }

  return temp.length === 0;
};