Marcy Blog

Failed to be a geek

Problem: Word Break

Question Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words....

Problem: Decode Ways

Question A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, dete...

Problem: Maximum Length of Repeated Subarray

Question Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays. Example 1: Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repe...

Problem: Maximum Subarray

Question Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,...

Problem: Minimum Path Sum

Question Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down ...

Problem: Best Time to Buy and Sell Stock

Question Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of ...

Problem: Min Cost Climbing Stairs

Question On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reac...

Problem: Maximal Square

Question Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area. Example: Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4 So...

Problem: Unique Paths II

Question A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to...

Problem: Climbing Stairs

Question You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will ...