Two Sum

Description:

Solution:

1. Using brute-force
2. Using BST to find complement ⇒ O(nlogn)

e

Add 2 Nums (linked list)

Description:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Solution:

• We keep going until list 1 and list 2 are both null and carry ≠ 0
• if list 1 ≠ null ⇒ val_list1 = list1.val , if not, val_list1= 0
• if list 2 ≠ null ⇒ val_list2 = list2.val , if not, val_list2= 0
• sum = val_list1 + val_list2 + carry ;
• create new node which value = sum %10
• carry = sum/10
• return the head of new list .next

1. Longest Substring Without Repeating Characters

Description:

Given a string s, find the length of the longest substring without duplicate characters.

Solution:

• Using List
• Keep checking sub string whenever encounter duplicate

Longest Palindromic Substring (DP, 2 pointers) - not done

Description:

Given a string s, return the longest palindromic substring in s.

Solution:

1. Using 2 pointers

Zigzag Conversion

Description:

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

Solution:

1. Using Brute-force

   We build number of rows that we need

   We append character to every row

   Using direction variable (1 is going up and -1 is going down)

   If we hit 0 ( currentRow = 0 ⇒ change direction)

   If we hit numRow-1 ( currentRow = numRows-1 ⇒ change direction)

Reverse Integer

Description:

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Solution:

1. Using String to reverse (only if test case input is small)
2. Using math

e

Palindrome Number

Description:

Given an integer x, return true if x is a palindrome, and false otherwise.

Solution:

1. Using 2 pointers

e

Description:

Solution:

Container With Most Water

Description:

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Solution:

1. Using 2 pointers

   We use 2 pointer left and right from 2 bounds

   we move the pointer whose value less than another

   while moving pointers we count area assign to max

   when pointer left across right ⇒ return max

Integer to Roman

Description: Convert from Integer to Roman

Solution:

1. Using Hashmap
   1. We keep iterating the map which stores value of Roman character
2. Using 2D array to store

Roman to Integer

Description: Convert from Roman to Integer ( reverse version of 12)

Solution:

Scan from the right to left

If the previous larger than the current ⇒ we add it

if the previous is smaller or equal to the current ⇒ we subtract it

Longest Common Prefix

Description:

Solution:

3 Sum

Description:

Solution:

1. Using 3 loops ( bad)
2. Using 2 pointers + sorting

3Sum Closest

Description:

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Solution: ( similar to 15)

1. We using 2 pointers and sorting

Letter Combinations of a Phone Number

4 Sum

Remove Nth Node From End of List (linked list)

Valid Parentheses