Tag Archives: leetcode

LeetCode 206. Reverse Linked List

Here is a quick solution to Reverse Linked List problem.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let curr = head;
    let prev = null;

    while (curr) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
};

LeetCode 560. Subarray Sum Equals K

Brute Force Solution to Subarray Sum Equals K problem from LeetCode:

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let ans = 0;

    for (let i=0; i<nums.length; i++) {
        let currSum = nums[i];
        if (currSum === k) ans++;
        for (let j=i+1; j<nums.length; j++) {
            currSum += nums[j];
            if (currSum === k) ans++;

        }
    }

    return ans;
};

Optimized solution after cheating a bit:

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let ans = 0;
    const m = new Map();
    let sum=0;
    m.set(sum, 1);

    for (let i=0; i<nums.length; i++) {
        sum += nums[i];

        if (m.has(sum-k)) {
            ans += m.get(sum-k);
        }

        if (!m.has(sum)) {
            m.set(sum, 1);
        } else {
            m.set(sum, m.get(sum) + 1);
        }

    }

    return ans;
};

Runtime: 96 ms, faster than 94.76% of JavaScript online submissions for Subarray Sum Equals K.

Memory Usage: 46.6 MB, less than 81.14% of JavaScript online submissions for Subarray Sum Equals K.

LeetCode 2. Add Two Numbers

Here is my solution to Add Two Numbers problem in PHP:

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $ans = new ListNode(0, null);
        $p = $l1;
        $q = $l2;
        $current = $ans;
        $carry=0;

        while ($p != null || $q != null) {
            $x = isset($p) ? $p->val : 0;
            $y = isset($q) ? $q->val : 0;
            $sum = $carry + $x + $y;
            $carry = (int) ($sum/10);
            $current->next = new ListNode($sum%10);
            $current = $current->next;
            if ($p != null) $p = $p->next;
            if ($q != null) $q = $q->next;
        }
        if ($carry > 0) {
            $current->next = new ListNode($carry);
        }

        return $ans->next;
    }
}

LeetCode 7. Reverse Integer

My initial solution for Reverse Integer problem:

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {

    let ans = '';
    if (x<0) {
        ans = '-';
        x*=-1;
    }

    str = x.toString();

    for (let i=str.length-1; i>=0; i--) {
        ans += str[i];
    }

    ans = parseInt(ans);
    if (ans>2**31-1 || ans<(-2)**31) {
        return 0;
    }
    return ans;
};

Results

Runtime: 104 ms, faster than 34.78% of JavaScript online submissions for Reverse Integer.

Memory Usage: 40.5 MB, less than 33.80% of JavaScript online submissions for Reverse Integer.

Optimized Version:

After looking at solution and transpiling it to JavaScript:

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {

    const max = 2**31-1;
    const min = (-2)**31;
    let ans = 0;

    while (x != 0) {
        const pop = x%10;
        x = Math.trunc(x/10);
        if (ans > max/10) return 0;
        if (ans < min/10) return 0;

        ans = ans * 10 + pop;
    }

    return ans;
};

Optimized Results

Runtime: 92 ms, faster than 87.08% of JavaScript online submissions for Reverse Integer.

Memory Usage: 40.4 MB, less than 33.80% of JavaScript online submissions for Reverse Integer.

LeetCode 3. Longest Substring Without Repeating Characters

Here is my solution in PHP to this problem.

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $n = strlen($s);
        $ans = 0;
        $i = 0;
        $j = 0;

        $arr = [];

        while ($i < $n && $j < $n) {
            if (!in_array($s[$j], $arr)) {
                $arr[] = $s[$j++];
                $ans = max($ans, $j-$i);
            } else {
                array_splice($arr, 0, 1);
                $i++;
            }
        }


        return $ans;
    }
}

And here is solution JavaScript based on this Udemy lesson:

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if (s.length <= 1) return s.length;

    const seenChars = {};
    let i=0, longest=0;

    for (let j=0; j<s.length; j++) {
        const currentChar = s[j];
        const currentCharIndex = seenChars[currentChar];

        if (currentCharIndex>=i) {
            i = currentCharIndex+1;
        }

        longest = Math.max(longest, j-i+1);
        seenChars[currentChar] = j;
    }

    return longest;
};

LeetCode 1664: Ways to Make a Fair Array

I tried to do this all by myself but got stuck, ended up transpiling this solution in PHP.

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function waysToMakeFair($nums) {
        $len = count($nums);
        $ans = 0;

        $leftOdd = 0;
        $rightOdd = 0;
        $leftEven = 0;
        $rightEven = 0;

        for ($i=0; $i<$len; $i++) {
            if ($i%2 === 0)
                $rightEven += $nums[$i];
            else
                $rightOdd += $nums[$i];
        }

        for ($i=0; $i<$len; $i++) {
            if ($i%2 === 0)
                $rightEven -= $nums[$i];
            else
                $rightOdd -= $nums[$i];

            if ($leftEven + $rightOdd === $rightEven + $leftOdd) $ans++;

            if ($i%2 === 0)
                $leftEven += $nums[$i];
            else
                $leftOdd += $nums[$i];
        }

        return $ans;
    }
}

LeetCode 20: Valid Parentheses

Here is my solution to this problem in PHP:

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stack = [];
    const brackets = {
        '(': ')',
        '{': '}',
        '[': ']'
    };

    for (i=0; i<s.length; i++) {
        if (s.length === 0) return true;

        const c = s[i];
        if (brackets[c]) {
            stack.push(c);
        } else {
            const lastBracket = stack.pop();
            if (brackets[lastBracket] !== c) return false;
        }
    }

    if (stack.length > 0) return false;

    return true;
};

LeetCode 844. Backspace String Compare

Here is my solution Backspace String Compare problem.

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    s = processString(s);
    t = processString(t);
    //console.log({s, t})
    return s===t;
};

let processString = function(s) {
    const a = [];
    let skip = 0;
    for (let i = s.length-1; i >= 0; i--) {
        if (s[i] === '#') {
            skip++;
        } else if (skip > 0) {
            skip--;
        } else {
            a.push(s[i]);
        }
        //console.log({a, skip, i})
    }
    let re = '';
    //console.log({ a: a.length})
    while (a.length > 0) {
        re += a.pop();
        //console.log({i, re, a: a.length})
    }
    return re;
}

Results:

Runtime: 80 ms, faster than 73.76% of JavaScript online submissions for Backspace String Compare.

Memory Usage: 39.3 MB, less than 33.63% of JavaScript online submissions for Backspace String Compare.

Leetcode 690: Employee Importance Solution

Here is another LeetCode solution for Employee Importance Problem.

/**
* Definition for Employee.
* class Employee {
*     public $id = null;
*     public $importance = null;
*     public $subordinates = array();
*     function __construct($id, $importance, $subordinates) {
*         $this->id = $id;
*         $this->importance = $importance;
*         $this->subordinates = $subordinates;
*     }
* }
*/

class Solution {
/**
 * @param Employee[] $employees
 * @param Integer $id
 * @return Integer
 */

function getImportance($employees, $id) {
  if (empty($employees)) return 0;
  $emap = [];
  foreach ($employees as $e) {
    $emap[$e->id] = $e;
  }

  return $this->recurse($emap, $id);
 }

function recurse($emap, $id) {
  $e = $emap[$id];
  $ans = $e->importance;
  foreach ($e->subordinates as $sub) {
    $ans += $this->recurse($emap, $sub);
  }
  return $ans;
 }
}

LeetCode 1249. Minimum Remove to Make Valid Parentheses

Here is my solution to this problem:

/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function(s) {
    const stack = [];
    const charArray = s.split("");
    const rightBracketsToRemove = [];

    for (let i=0;i<charArray.length;i++) {
        if (charArray[i] === '(') {
            stack.push(i);
        } else if (charArray[i] === ')' && stack.length > 0) {
            stack.pop();
        } else if (charArray[i] === ')') {
            charArray[i] = '';
        }
    }

    while (stack.length > 0) {
        const i = stack.pop();
        charArray[i] = '';
    }

    return charArray.join('');
};