sum: represents the remaining path sum from current node to leaf node before the current node is taken into consideration. That's why for the leaf node, we need to do sum - root.val == 0
If there are n nodes in binary tree, maximum height of the binary tree is
n-1and minimum height isfloor(log_2(n)).For example, left skewed binary tree shown in Figure 1(a) with 5 nodes has height 5-1 = 4 and binary tree shown in Figure 1(b) with 5 nodes has height floor(log(25)) = 2.
- time:
O(n) - Space: height of the tree.
- Best case:
O(log_2(n)), - Worst case:
O(n)(the tree is skewed tree)
- Best case:
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null && root.val == targetSum) return true;
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
}
- Define a fast pointer and a slow pointer
- Make the slow pointer move till the middle,
- reverse slow.next
- Firsthalf pointing at the head, secondhalf pointing at reverse(slow.next)
- Check each element on the 1/2 and 1/2 of the linkedlists , to see if they are the same.
- Time: O(1.5n)
- Space: O(1.5n) = O(n)
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
//fast and slow pointers:
ListNode fast = head, slow = head;
while (fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode secondHalf = reverse(slow.next);
ListNode firstHalf = head;
//check if fast and "slow -> fast" parts are the same
while(firstHalf != null && secondHalf != null){
if(firstHalf.val != secondHalf.val) return false;
secondHalf = secondHalf.next;
firstHalf = firstHalf.next;
}
return true;
}
public ListNode reverse(ListNode head){
ListNode newHead = null;
while (head != null){
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}
}- Time: O(n)
- Space: O(n). Because in recursion methods, And the height of the stack is based on the number of nodes. So it use linear space.
Example :
1-> 2-> 3-> 4-> 2-> 1
ref points 1 initially.
Make recursive calls until you reach the last element - 1.
On returning from each recurssion, check if it is equal to ref values.
ref values are updated to on each recurssion.
So first check is ref 1 - end 1
Second ref 2 - second last 2 ...and so on.
class Solution {
ListNode ref;
public boolean isPalindrome(ListNode head) {
ref = head;
return check(head);
}
public boolean check(ListNode node){
if(node == null) return true;
boolean ans = check(node.next);
boolean isEqual = (ref.val == node.val)? true : false;
ref = ref.next;
return ans && isEqual;
}
}- Time: O(n)
- Space: O(1)
First, we get the prefix sum each time we loop through the array
- Track the minimum prefixSum between the curr minimum and each prefixSum
- And then return the difference between 1 and that minimum value, simply by
1- min.
class Solution {
public int minStartValue(int[] nums) {
//Return the minimum positive value of startValue such that the step by step sum is never less than 1.
/*
prefix sum
Get the smallest value of all the sums starting from index 0 to nums.length - 1
if it's negative, we get its absolute value, then plus 1
if it's positive, we plus 1
*/
if (nums == null) {
throw new IllegalArgumentException("Input array is null");
}
int min = 0;
int prefixSum = 0;
for(int i = 0; i < nums.length; i ++){
prefixSum += nums[i];
// Find the minimum prefix sum which is <= zero, as it will help us to find the lowest negative value.
min = Math.min(min, prefixSum);
}
return 1 - min;
}
}- time: Math.max(26, word1.length()) - O(n)
- Space: O(52) - O(n)
class Solution {
public boolean checkAlmostEquivalent(String word1, String word2) {
int[] one = new int[26];
int[] two = new int[26];
for(int i = 0; i < word1.length(); i ++){
one[word1.charAt(i) - 'a'] ++;
two[word2.charAt(i) - 'a'] ++;
}
for(int j = 0; j < 26; j ++){
if (Math.abs(one[j] - two[j]) > 3){
return false;
}
}
return true;
}
}- Time: O(Math.max(word1.length, max of #unique characters));
- Space: O(max of #unique characters)
public boolean checkAlmostEquivalent(String word1, String word2) {
Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i < word1.length(); i ++){
map.put(word1.charAt(i), map.getOrDefault(word1.charAt(i), 0) + 1);
map.put(word2.charAt(i), map.getOrDefault(word2.charAt(i), 0) - 1);
}
for(int v: map.values()){
if (Math.abs(v) > 3){
return false;
}
}
return true;
}Base cases:
-
if n <= 0, then the number of ways should be zero.
-
if n == 1, then there is only way to climb the stair.
-
if n == 2, then there are two ways to climb the stairs. One solution is one step by another; the other one is two steps at one time.
-
[n] = [n-1] + [n-2], because from the [n-1] point, we can take 1 step to reach [n], and from the [n-2] point, we could take 2 steps to get there. -
Time complexity: O(n)
-
Space complexity: O(n)
public int climbStairs(int n) {
int[] dp = new int[n+1];
if (n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i ++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}base case: F(0) = 0, F(1) = 1
dp[i] = dp[i-1] + dp[i-2];
- Time complexity: O(n)
- Space complexity: O(n)
public int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 1;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i ++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
- while n is greater than 1:
- let sum becomes the previous 2 items' sum
- and let the previous first item becomes the second item
- let second item becomes sum, then iterative
- Time complexity: O(n)
- Space complexity: O(1)
if(N <= 1) return N;
int a = 0, b = 1;
while(N-- > 1){
int sum = a + b;
a = b;
b = sum;
}
return b;
else, return fib(N - 1) + fib(N - 2)
- Time complexity: O(2^n)- since T(n) = T(n-1) + T(n-2)is an exponential time
- Space complexity: O(n) - space for recursive function call stack
public int fib(int N){
if(N <= 1) return N;
else
return fib(N - 1) + fib(N - 2);
}- Time complexity: number of characters in the input String. --> O(n)
- Space complexity: s.length()--> O(n)
class Solution {
public int lengthOfLastWord(String s) {
Stack<String> stack = new Stack<>();
for(String word:s.split(" ")){
stack.push(word);
}
return stack.pop().length();
}
}- Time complexity: O(last word)
- Space complexity: O(1)
class Solution {
public int lengthOfLastWord(String s) {
int length = 0;
for (int i = s.length() - 1; i >= 0; i --){
if (s.charAt(i) != ' '){
length ++;
}else{
if (length > 0){
return length;
}
}
}
return length;
}
}- Time complexity: O(mn log (n))
- Space complexity: O(n)
- First, we define a prev one to be the sorted anagram.
- And only when they are different could we add it to our final list, else, we skip it.
- Update the prev every time
class Solution {
public List<String> removeAnagrams(String[] words) {
List<String> list = new ArrayList<>();
String prev = "";
for(int i = 0; i < words.length; i++){
char[] ch = words[i].toCharArray();
Arrays.sort(ch);
String curr = new String(ch);
if (!curr.equals(prev)){
list.add(words[i]);
prev = curr;
}
}
return list;
}
}Given an array of integers arr, you’re asked to calculate for each index i the product of all integers except the integer at that index (i.e. except arr[i]). Implement a function arrayOfArrayProducts that takes an array of integers and returns an array of the products.
Solve without using division and analyze your solution’s time and space complexities.
Examples:
input: arr = [8, 10, 2]
output: [20, 16, 80] # by calculating: [10*2, 8*2, 8*10]
input: arr = [2, 7, 3, 4]
output: [84, 24, 56, 42] # by calculating: [7*3*4, 2*3*4, 2*7*4, 2*7*3]
- Time: O(n)
- Space: O(n)
static int[] arrayOfArrayProducts(int[] arr) {
// your code goes here
/*
0---> i - 1 product
i + 1 --> arr.length - 1
*/
if (arr.length == 0){
return arr;
}
if (arr.length == 1) {
return new int[0];
}
int[] result = new int[arr.length];
int product1 = 1;
result[0] = 1;
for(int i = 1; i < arr.length; i ++){
product1 *= arr[i-1];
result[i] = product1;
}
int product2 = 1;
for(int i = arr.length - 2; i >= 0; i--){
product2 *= arr[i + 1];
result[i]*=product2;
}
return result;
}- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity:
- Time complexity:
- Space complexity: