[LeetCode] Maximum Product Subarray

Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution:O(n)

public class Solution {

    public int maxProduct(int[] A) {
        if(A.length == 1)
            return A[0];
            
        int max = A[0];
        int premax = Math.max(A[0],0);
        int premin = Math.min(A[0],0);
        for(int i=1; i=0){
              premax = (premax ==0?A[i]: A[i]*premax);
              premin = (premin ==0?0: A[i]*premin);
            }
            else{
              int tmp = (premin ==0? 0 : A[i]*premin);
              premin = (premax > 0? A[i]*premax: A[i]);
              premax = tmp;
            }
            max = Math.max(max,premax);
        }
        return max;
    }
}

[LeetCode] Reverse Words in a String

Problem:

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Solution:O(n)

[LeetCode] Evaluate Reverse Polish Notation

Problem:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:O(n)

[LeetCode] Max Points on a Line

Problem:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution:O(n*n)

[LeetCode] Sort List

Problem:
Sort a linked list in O(n log n) time using constant space complexity.
Solution:O(nlogn)

[LeetCode] Insertion Sort List

Problem:
Sort a linked list using insertion sort.
Solution:O(n*n)

[LeetCode] LRU Cache

Problem:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution:O(1)

[LeetCode] Binary Tree Postorder Traversal

Problem:

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution:O(n)

[LeetCode] Binary Tree Preorder Traversal

Problem:

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Solution:O(n)

[LeetCode] Linked List Cycle II

Problem:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

Solution:O(n)

[LeetCode] Linked List Cycle

Problem:

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Solution:O(n)

[LeetCode] Reorder List

Problem:

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution:O(n)

[LeetCode] Word Break II

Problem:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution:O(n*n)

[LeetCode] Word Break

Problem:

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Solution:O(n*n)

[LeetCode] Copy List with Random Pointer

Problem:

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.

Solution:O(n)

[LeetCode] Single Number II

Problem:

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:O(n)

[LeetCode] Single Number

Problem:

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:O(n)

[LeetCode] Candy

Problem:

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Solution:O(n)

[LeetCode] Gas Station

Problem:

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 station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

Solution:O(n)

[LeetCode] Clone Graph

Problem:

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution:O(n)