CTCI

#Leetcode

• SelfCrossing

• Move Zeroes Move zeroes in an array towards the end without changing the original position of elements

• Invert tree Rotate all nodes in a tree such that the left node becomes the right and the right becomes the left node.

• Remove node from LL Remove a node from LL given access to only that node. LinkedList.java -> removeNodeFromLL

• Same Tree Given two binary trees, write a function to check if they are equal or not.

• Anagrams Given two strings s and t, write a function to determine if t is an anagram of s.

• Array Duplicates Given an array of integers, find if the array contains any duplicates

• Excel Sheet Column Number Given a column title as appear in an Excel sheet, return its corresponding column number

• Majority Element Majority element in an array

• LinkedList Reverse Part of Code/LinkedList.java

• Lowest Common Ancestor BinarySearchTree.lowestAncestor()

• Hamming Weight Number of 1 Bits

• Power of three Given an integer, write a function to determine if it is a power of three.

• Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top.

• Power of two Given an integer, write a function to determine if it is a power of two.

• Buy Sell 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 the stock), design an algorithm to find the maximum profit.

• Merge two lists LinkedList.mergeTwoLists class

• Reverse vowels in a string

• House Robber 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 list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

• Balanced Binary Tree For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1

• Remove element Given an array and a value, remove all instances of that value in place and return the new length.

• Queue using stacks Code.QueueUsingTwoStacks

• Symmetric tree SerializeBST.isSymmetric()

• Binary Tree Level Order Traversal II SerializeBST.levelOrderBottom()

• PlusOne Given a non-negative number represented as an array of digits, plus one to the number

• Pascal Triangle Given numRows, generate the first numRows of Pascal's triangle.

• Power of four Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

• Remove Duplicates from Sorted Array Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

• Factorial Trailing Zeroes Given an integer n, return the number of trailing zeroes in n!.

• Pascals Traingle 2.0 Given an index k, return the kth row of the Pascal's triangle.

• Valid Soduko Determine if a Sudoku is valid

• Minimum depth of a Binary Tree(SerializeBST.minDepth) Given a binary tree, find its minimum depth. (Note : Check this solution again)

• Bulls and Cow Bulls and Cows the game

• Implement Stack using Queues Implement Stack using Queues

• Isomorphic strings egg and add are isomorphic. title and paper too. this and when aren't.

• Binary Tree Paths Given a binary tree, return all root-to-leaf paths

• Merge Sorted Arrays Merged Two Sorted Arrays Fam

• Remove Nth Node From End of List (LL.removeNthFromEnd) Given a linked list, remove the nth node from the end of list and return its head.

• Word Pattern Given a pattern and a string str, find if str follows the same pattern.

• Valid Parenthesis

• Count and Say The count-and-say sequence is the sequence of integers beginning as follows:1, 11, 21, 1211, 111221, ...

• Guess higher or lower

• Length of last word Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

• ZigZag Conversion The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows and then read line by line: "PAHNAPLSIIGYIR"

• Valid Palindrome Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

• Reverse Integer Reverse digits of an integer with consideration for overflow

• Min Stack Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• First Bad Version Find the first bad version in a list of versions.

• Excel sheet column title Given a positive integer, return its corresponding column title as appear in an Excel sheet.

• Rotate Array 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].

• Compare version number Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

• String to integer Implement atoi to convert a string to an integer. example : 1234(String) -> 1234(int)

• Counting Bits Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary . For example : For num = 5 you should return [0,1,1,2,1,2].

• Linkedlist random node Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen

• Single Numbers 3 Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

• Shuffle Array Shuffle a set of numbers without duplicates.

• Product of Array except self.

• Top K Frequent Elements Given a non-empty array of integers, return the k most frequent elements.

  For example, Given [1,1,1,2,2,3] and k = 2, return [1,2].

• Best Time to Buy and Sell Stock II Say you have an array for which the ith element is the price of a given stock on day i.

• Count Numbers with Unique Digits Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

• Integer Break Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get

• Missing Number Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. For example, Given nums = [0, 1, 3] return 2.

• Pre Order using Stack SerializeBST.preOrderTraversal()

• Two Sum Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

• Bulb Switcher There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

• InOrder Traversal SerializeBST.inOrderTraversal()

• Kth Smallest Element in a Sorted Matrix Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

  matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,

  return 13

• Integer To Roman Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

• Odd Even Linked List(LL.oddEvenList()) Example: Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL.

• Kth Smallest Element in a BST Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. SerializeBST.kthSmallest()

• Sorted Array to BST SerializeBST.sortedArrayToBST()

• Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

• Combination Sum 3 Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Example 1: Input: k = 3, n = 7 Output : [[1,2,4]]

• Unique Binary Search Trees Given n, how many structurally unique BST's (binary search trees) that store values 1...n? For example, Given n = 3, there are a total of 5 unique BST's.

• Best Time to Buy and Sell Stock with Cooldown Example : prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell]

• Different Ways to Add Parentheses Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *. Example 1 Input: "2-1-1".

  ((2-1)-1) = 0 (2-(1-1)) = 2

• Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. [1,3,5,6], 5 → 2

• Gray Code Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

• Permutations Given a collection of distinct numbers, return all possible permutations.

• Unique Paths 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 reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there?

• Minimum in Rotated Array Suppose a sorted array is rotated at some pivot unknown to you beforehand.

• Maximum Subarray Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

• Right side view of BST SerialiseBST.rightSideView()

• Valid Perfect Square Given a positive integer num, write a function which returns True if num is a perfect square else False.

• Spiral Matrix Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

• Search a 2D Matrix II Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.

• Combinations Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

• Minimum Path Sum 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.

• Longest Increasing Subsequence Given an unsorted array of integers, find the length of longest increasing subsequence.For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4

• Sort Colors Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively

• Game of Life

• Increasing Triplet Sub Sequence Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

• Container With Most Water Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

• Kth Largest Element in an Array Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

• Search a 2D Matrix Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

• Peeking Iterator Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

• Find Peak Element A peak element is an element that is greater than its neighbors.

• Set Matrix Zeroes Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

• Wiggle Subsequence Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence

• Decode String Given an encoded string, return it's decoded string.s = "3[a]2[bc]", return "aaabcbc".

• Perfect Squares Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

  For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

• Remove Duplicates from Sorted Array II For example, Given sorted array nums = [1,1,1,2,2,3],

  Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

• Subsets Given a set of distinct integers, nums, return all possible subsets.

• Verify Preorder Serialization of a Binary Tree Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

• Combination Sum Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

• Lexicographical Numbers
  Given an integer n, return 1 - n in lexicographical order.

  For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

• Search in Rotated Sorted Array II Follow up for "Search in Rotated Sorted Array":What if duplicates are allowed?

• Bitwise AND of Numbers Range Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4.

• Subsets II Given a collection of integers that might contain duplicates, nums, return all possible subsets.

• House robber II After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle

• Largest Divisible Subset Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

• Guess Number Higher or Lower II Guess number + pay for the guessed number.

• Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

• Super pow Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

• Longest Substring with At Least K Repeating Characters Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

• H-Index Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

• Letter Combinations of a Phone Number Given a digit string, return all possible letter combinations that the number could represent.

• Ugly Number II Write a program to find the n-th ugly number.

• Unique Paths IIUnique Paths II Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be?

• Search for a Range Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). Given [5, 7, 7, 8, 8, 10] and target value 8,return [3, 4]

• 3Sum Closest Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

• Number of Islands Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

• Longest Absolute File Path

• Group Anagrams Given an array of strings, group anagrams together.

• Bit Manipulation Guide https://discuss.leetcode.com/topic/50315/a-summary-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently

• Intersection of Two Arrays II Given two arrays, write a function to compute their intersection. Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

• Longest Palindrome Given a string which consists of lowercase or uppercase, find the length of the longest palindromes that can be built with those letters.

• Add Strings Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2.

• Island Perimeter Find perimeter of a Matrix

• Fizz Buzz Write a program that outputs the string representation of numbers from 1 to n.

  But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

• Adding two numbers without + AddingWithBits.javas

• AssignCookies AssignCookies.java

• Minimum Moves to Equal Array Elements Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

• Longest Palindromic Substring Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.