Treasure Island II

You have a map that marks the locations of treasure islands. Some of the map area has jagged rocks and dangerous reefs. Other areas are safe to sail in. There are other explorers trying to find the treasure. So you must figure out a shortest route to one of the treasure islands. Assume the map area is a two dimensional grid, represented by a matrix of characters. You must start from one of the starting point (marked as S) of the map and can move one block up, down, left or right at a time.

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

Treasure Island

You have a map that marks the location of a treasure island. Some of the map area has jagged rocks and dangerous reefs. Other areas are safe to sail in. There are other explorers trying to find the treasure. So you must figure out a shortest route to the treasure island. Assume the map area is a two dimensional grid, represented by a matrix of characters. You must start from the top-left corner of the map and can move one block up, down, left or right at a time.

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

Repair Broken Edges of a Graph

There’s an undirected connected graph with n nodes labeled 1..n. But some of the edges has been broken disconnecting the graph. Find the minimum cost to repair the edges so that all the nodes are once again accessible from each other. Input n, an int representing the total number of nodes. edges, a list of integer pair representing the nodes connected by an edge. edgesToRepair, a list where each element is a triplet representing the pair of nodes between which an edge is currently broken and the cost of repearing that edge respectively (e.

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

Top K Frequent Words

Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first. Example 1 Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 Output: ["i", "love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.

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

Vertical Order Traversal of a Binary Tree

Given a binary tree, return the vertical order traversal of its nodes values. For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1). Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

by lek tin in "algorithm" access_time 2-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

Decode Ways II

A message containing letters from A-Z is being encoded to numbers using the following mapping way: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9. Given the encoded message containing digits and the character '*', return the total number of ways to decode it.

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

Is Graph Bipartite

Given an undirected graph, return true if and only if it is bipartite. Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B. The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists.

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

Sliding Puzzle

On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0. A move consists of choosing 0 and a 4-directionally adjacent number and swapping it. The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]]. Given a puzzle board, return the least number of moves required so that the state of the board is solved.

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