bfs:

Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1.

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

Clone Graph

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. Example: Input: {"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1} Explanation: Node 1's value is 1, and it has two neighbors: Node 2 and 4. Node 2's value is 2, and it has two neighbors: Node 1 and 3. Node 3's value is 3, and it has two neighbors: Node 2 and 4.

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

Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must 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 in a word. Example: Input: board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words = ["oath","pea","eat","rain"] Output: ["eat","oath"] Note All inputs are consist of lowercase letters a-z.

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

The Maze II

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction. Given the ball’s start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included).

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

The Maze

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction. Given the ball’s start position, the destination and the maze, determine whether the ball could stop at the destination. The maze is represented by a binary 2D array.

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

Snakes and Ladders

On an N x N board, the numbers from 1 to N*N are written boustrophedonically starting from the bottom left of the board, and alternating direction each row. For example, for a 6 x 6 board, the numbers are written as follows: You start on square 1 of the board (which is always in the last row and first column). Each move, starting from square x, consists of the following:

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

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.

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

Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language. Example 1 Input: [ "wrt", "wrf", "er", "ett", "rftt" ] Output: "wertf" Example 2 Input: [ "z", "x" ] Output: "zx" Example 3 Input: [ "z", "x", "z" ] Output: "" Explanation The order is invalid, so return "".

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

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees. Example 1 Input: 2 / \ 1 3 Output: true Example 2 5 / \ 1 4 / \ 3 6 Output: false Explanation The input is: [5,1,4,null,null,3,6].

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

Word Ladder

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.

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