Flood Fill

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535). Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image. To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on.

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

Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below. Flatten the list so that all the nodes appear in a single-level, doubly linked list.

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

Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.

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

Populating Next Right Pointers in Each Node II

Given a binary tree struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Follow up You may only use constant extra space. Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

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

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Note There may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity? Solution (Bottom-up) Python

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

PowX N

Example 1 Input: 2.00000, 10 Output: 1024.00000 Example 2 Input: 2.10000, 3 Output: 9.26100 Example 3 Input: 2.00000, -2 Output: 0.25000 Explanation 2-2 = 1/22 = 1/4 = 0.25 Note -100.0 < x < 100.0 n is a 32-bit signed integer, within the range [−231, 231 − 1] Solution # Time: o(logN) # Space: `O(n)` class Solution: def myPow(self, x, n): """ :type x: float :type n: int :rtype: float """ if n > 0: return self.

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

Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the : “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4] _______3______ / \ ___5__ ___1__ / \ / 6 _2 0 8 / 7 4

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

Invert Binary Tree

Invert a binary tree. 4 / \ 2 7 / \ / \ 1 3 6 9 to 4 / \ 7 2 / \ / \ 9 6 3 1 Thoughts What if a node is NULL? A NULL has no children, so how to iterate deeper into the tree? Solution // Attempt // class Solution { // public: void swapNodes(*leftNode, *rightNode) { *temp = *leftNode; *leftNode = *rightNode; *rightNode = temp; return; } TreeNode* invertTree(TreeNode* root) { if (root == NULL) return invertTree(root->left) } }; Solution C++

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

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping: ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1 Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2 Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

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