Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode dummy = new ListNode(0); ListNode temp = dummy; while (l1 !

by lek tin in "algorithm" access_time 2-min read

Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

by lek tin in "algorithm" access_time 1-min read

Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Example 1 Input: num1 = "2", num2 = "3" Output: "6" Example 2 Input: num1 = "123", num2 = "456" Output: "56088" Note The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself.

by lek tin in "algorithm" access_time 1-min read

Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note You may assume k is always valid, 1 ≤ k ≤ BST's total elements. Example 1 Input: root = [3,1,4,null,2], k = 1 Output: 1 Example 2 Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3 ``` ### Follow-up What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently?

by lek tin in "algorithm" access_time 2-min read

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1 Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2 Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4 Note You may assume k is always valid, 1 ≤ k ≤ array's length. Solution Average time complexity: O(n) if we don’t need the sorted output, otherwise O(n+kLogk)

by lek tin in "algorithm" access_time 2-min read

Group Anagrams

Given an array of strings, group anagrams together. Example Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note All inputs will be in lowercase. The order of your output does not matter. Solution (naive) Time: O(Nklogk), k: length of the longest word Space: O(Nk) sort each word and use it the sorted str as a key to the lookup dictionary class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: ans = collections.

by lek tin in "algorithm" access_time 2-min read

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space? Observation: Solution: /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if (head == null) return null; ListNode slow = head; ListNode fast = head; boolean hasCycle = false; while (slow.

by lek tin in "algorithm" access_time 2-min read

Linked List Cycle

Given a linked list, determine if it has a cycle in it. Follow-up Can you solve it without using extra space? Solution # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ slow = head fast = head while fast: # fast reaches the end, no cycle was detected if fast and not fast.

by lek tin in "algorithm" access_time 1-min read

Compare Version Numbers

Compare two version numbers version1 and version2. If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

by lek tin in "algorithm" access_time 1-min read

Word Search

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Example board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = "ABCCED", return true. Given word = "SEE", return true. Given word = "ABCB", return false.

by lek tin in "algorithm" access_time 2-min read