For the given island that’s represented in a matrix of 0's and 1's, we usually use a depth-first search or a breadth-first search algorithm to solve. Today, I’ll introduce how to solve and compare such a problem using both approaches.

Problem

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example:


The sliding window algorithm is often used to find the target number in a string/list. Today, I’ll introduce how to solve this leetcode problem using the sliding window algorithm and optimize its running time.

Problem description

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7]…

We know tree well, a binary search tree performs well in searching. Today, I’ll introduce another tree-like data structure, which is widely used for retrieval of a key in a dataset of strings: trie.

Introduction

A trie also called prefix-tree, is a type of search tree, a tree data structure used for locating specific keys from within a set. These keys are always strings and characters. A trie is structured by trie nodes. …


My previous post introduced the Knapsack problem. It states how to solve using the dynamic programming algorithm. Besides Knapsack, there’s one series of problems that you might encounter in a coding interview: the house robber problems. Today, let’s talk about it.

Problem description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a…


Dynamic programming problems are frequently asked in a tech interview. For me, dynamic programming problems are challenging to understand and to solve. Recently, I see a post demonstrating that dynamic programming problems can be categorized. One of the categories is the Knapsack problem. Today, I'll introduce what’s knapsack problem and its related topics.

Definition

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and…


It’s often asked during a technical interview: write a function to get the subsets/combinations/permutations for a given set. These problems seem difficult to solve in the first place, but have similarities when applying the backtracking algorithm. In this post, I’ll illustrate how to solve these problems using the backtracking algorithm.

Definitions

Assume we are given a set A, and it contains several elements. For example, A = [1, 2, 3].


For a given string, to get the minimum substring that contains all the characters we want is not easy to do. When screening through the string, we always use an algorithm called “sliding window” which uses two pointers to locate the substring. In this post, I’ll introduce this algorithm by solving this problem together: minimum window substring.

Problem Description

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there…


It’s a quite common problem in real life: how to find the minimum number of coins, to pay a specific amount with coins of different denominations? When I first see this problem in Leetcode, it took me a while to figure it out. After learning more about dynamic programming, I found it’s easy to understand and solve this problem. In this post, I'll introduce the algorithm and code to solve this classic problem.

Problem description

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need…


Problem description

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val

random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example:

Image for post
Image for post
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

You can solve this problem…


For the linear data structure, elements are inserted/deleted in a specific order. For example, the queue follows FIFO(first-in-first-out) pattern, whereas the stack follows the FILO(first-in-last-out) pattern. In the real world, only following fixed rules will not solve problems. For instance, jobs sent to a printer are placed in a queue. If we have a really important job that’s needed immediately, we might want the job to be run as soon as the printer is available. This particular scenario needs a special kind of queue, known as a priority queue. …

Wangyy

on the way to become a programmer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store