Marcy Blog

Failed to be a geek

Problem: Gas Station

Question There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank, and it costs cost[i] of gas to travel from sta...

Problem: Product of Array Except Self

Question Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without divisio...

Problem: Maximum Product of Three Numbers

Question Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1: Input: [1,2,3] Output: 6 Example 2: Input: [1,2,3,4] Output: 24 Solution...

Problem: Spiral Matrix

Question Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, ...

Problem: Rotate Image

Question You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image in-place, which means you have to modify the input...

Problem: Shortest Word Distance

Question Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list. Example: Assume that words = [“practice”, “makes”, “perfect”, “codi...

Problem: Rotate Array

Question Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. Solution We could solve the problem b...

Problem: Partition Labels

Question A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers re...

Problem: Find the Celebrity

Question Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him...

Problem: Set Matrix Zeros

Question Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place. Solution The idea is simple: Store states of each row in the first of that row, and store s...