pepe57
diff --git a/‎leetcode-solutions/BasicCalculator.java
Lines changed: 49 additions & 0 deletions b/‎leetcode-solutions/BasicCalculator.java
Lines changed: 49 additions & 0 deletions
diff --git a/‎leetcode-solutions/addStrings.java
Lines changed: 17 additions & 28 deletions b/‎leetcode-solutions/addStrings.java
Lines changed: 17 additions & 28 deletions
diff --git a/‎leetcode-solutions/basicCalculatorII.java
Lines changed: 38 additions & 4 deletions b/‎leetcode-solutions/basicCalculatorII.java
Lines changed: 38 additions & 4 deletions
diff --git a/‎leetcode-solutions/checkIfTwoStringAreEquivalent.java
Lines changed: 57 additions & 0 deletions b/‎leetcode-solutions/checkIfTwoStringAreEquivalent.java
Lines changed: 57 additions & 0 deletions
diff --git a/‎leetcode-solutions/cloestBinarySearchTreeValue.java
Lines changed: 54 additions & 0 deletions b/‎leetcode-solutions/cloestBinarySearchTreeValue.java
Lines changed: 54 additions & 0 deletions
diff --git a/‎leetcode-solutions/commonlyUsedCode.java
Lines changed: 55 additions & 0 deletions b/‎leetcode-solutions/commonlyUsedCode.java
Lines changed: 55 additions & 0 deletions
@@ -0,0 +1,49 @@
+Given a string s representing a valid expression, implement a basic calculator to evaluate it,
+ and return the result of the evaluation.
+
+Example 1:
+
+Input: s = "1 + 1"
+Output: 2
+Example 2:
+
+Input: s = " 2-1 + 2 "
+Output: 3
+Example 3:
+
+Input: s = "(1+(4+5+2)-3)+(6+8)"
+Output: 23
+
+USE A Stack
+TC: O(N)
+SC: O(N)
+
+class Solution {
+public static int calculate(String s) {
+	int len = s.length(), sign = 1, result = 0;
+	Stack<Integer> stack = new Stack<Integer>();
+	for (int i = 0; i < len; i++) {
+		if (Character.isDigit(s.charAt(i))) {
+			int sum = s.charAt(i) - '0';
+			while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
+				sum = sum * 10 + s.charAt(i + 1) - '0';
+				i++;
+			}
+			result += sum * sign;
+		} else if (s.charAt(i) == '+')
+			sign = 1;
+		else if (s.charAt(i) == '-')
+			sign = -1;
+		else if (s.charAt(i) == '(') {
+			stack.push(result);
+			stack.push(sign);
+			result = 0;
+			sign = 1;
+		} else if (s.charAt(i) == ')') {
+			result = result * stack.pop() + stack.pop();
+		}
+
+	}
+	return result;
+}
+}
@@ -1,44 +1,33 @@
-Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
+// Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
 
-Note:
+// Note:
 
-The length of both num1 and num2 is < 5100.
-Both num1 and num2 contains only digits 0-9.
-Both num1 and num2 does not contain any leading zero.
-You must not use any built-in BigInteger library or convert the inputs to integer directly.
+// The length of both num1 and num2 is < 5100.
+// Both num1 and num2 contains only digits 0-9.
+// Both num1 and num2 does not contain any leading zero.
+// You must not use any built-in BigInteger library or convert the inputs to integer directly.
 
 //TC: O(n) where n is max length of two arrays, because we loop through them bothß
 //SC: O(n) where n is max length between num1 and num2 to store char array
 class Solution {
     public String addStrings(String num1, String num2) {
-        char[] nums1 = num1.toCharArray();
-        char[] nums2 = num2.toCharArray();
-        
-        StringBuilder sb = new StringBuilder();
-        
-        int carry = 0; 
-        
-        int i =nums1.length-1;
-        int j =nums2.length-1;
-        
-        while(i>=0 || j>=0){
-            int sum = carry; 
+        int i=num1.length()-1;
+        int j = num2.length() -1;
+        int carry = 0;
+        StringBuilder res = new StringBuilder();
+        while(i>=0 ||  j>=0 || carry > 0){
+            int sum = carry;
             if(i>=0){
-                sum+= nums1[i] - '0';
+                sum += num1.charAt(i) - '0'; 
                 i--;
             }
             if(j>=0){
-                sum+= nums2[j] -'0';
+                sum+=num2.charAt(j) - '0';
                 j--;
             }
-            carry = sum/10; 
-            sb.append(sum%10);
+            carry = sum/10;
+            res.append(sum%10);
         }
-        if(carry >0){
-            sb.append(carry);
-        }
-        
-        sb.reverse(); 
-        return sb.toString();
+        return res.reverse().toString();
     }
 }
@@ -17,7 +17,9 @@
 // Output: 5
 
 
-USE A STACK 
+USE A STACK and keep track of sign
+TC: O(N) where N is length of string
+SC: O(N) where N is length of string
 
 public class Solution {
 public int calculate(String s) {
@@ -49,9 +51,41 @@ public int calculate(String s) {
     }
 
     int re = 0;
-    for(int i:stack){
-        re += i;
+    while(!stack.isEmpty()){
+        re += s.pop();
     }
     return re;
 }
-}
+}
+
+OPTIMIZED without the stack, use a "LAST NUMBER" to represent the stack
+TC: O(N)
+SC: O(1)
+class Solution {
+    public int calculate(String s) {
+        if (s == null || s.isEmpty()) return 0;
+        int length = s.length();
+        int currentNumber = 0, lastNumber = 0, result = 0;
+        char operation = '+';
+        for (int i = 0; i < length; i++) {
+            char currentChar = s.charAt(i);
+            if (Character.isDigit(currentChar)) {
+                currentNumber = (currentNumber * 10) + (currentChar - '0');
+            }
+            if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || i == length - 1) {
+                if (operation == '+' || operation == '-') {
+                    result += lastNumber;
+                    lastNumber = (operation == '+') ? currentNumber : -currentNumber;
+                } else if (operation == '*') {
+                    lastNumber = lastNumber * currentNumber;
+                } else if (operation == '/') {
+                    lastNumber = lastNumber / currentNumber;
+                }
+                operation = currentChar;
+                currentNumber = 0;
+            }
+        }
+        result += lastNumber;
+        return result;
+    }
+}
@@ -0,0 +1,57 @@
+Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.
+
+A string is represented by an array if the array elements concatenated in order forms the string.
+
+BUILD UP TWO STRINGS and compare, can use stringbuilder
+
+TC: O(N)
+SC: O(N)
+class Solution {
+    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
+        StringBuilder sb = new StringBuilder();
+        StringBuilder sb2 = new StringBuilder();
+        for(String s: word1){
+            sb.append(s);
+        }
+        for(String s: word2){
+            sb2.append(s);
+        }
+        
+        return sb.toString().equals(sb2.toString());
+    }
+}
+
+
+OPTMIZED, TWO POINTER, USE two nested pointers
+
+1) set of pointers for ith string we are on
+2) set of pointers for the first char we are currently on, which we will reset to 0
+
+TC: O(N)
+SC: O(1)
+
+public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
+	int p1 = 0, p2 = 0; // inner pointer for chars
+	int w1 = 0, w2 = 0; // outer pointer for the string we are on
+
+	while (w1 < word1.length && w2 < word2.length) {
+		String curr1 = word1[w1], curr2 = word2[w2];
+
+		if (curr1.charAt(p1) != curr2.charAt(p2)) return false;
+
+		if (p1 < curr1.length() - 1) {
+			p1++;
+		} else {
+			p1 = 0;
+			w1++;
+		}
+
+		if (p2 < curr2.length() - 1) {
+			p2++;
+		} else {
+			p2 = 0;
+			w2++;
+		}
+	}
+
+	return w1 == word1.length && w2 == word2.length;
@@ -0,0 +1,54 @@
+Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. 
+If there are multiple answers, print the smallest.
+
+
+Run binary search, since we are given a BST
+NOTE doesn't take care of printing smallest case
+
+TC: O(LogN)
+SC: O(1)
+
+class Solution {
+    public int closestValue(TreeNode root, double target) {
+        //binary search 
+        if(root == null) return 0; 
+        int closestVal = root.val; 
+        while(root != null){
+            if(Math.abs(target - root.val) < Math.abs(target - closestVal)){
+                closestVal = root.val; //UPDATE newly found closest value
+            } 
+
+
+            if (root.val > target){ //binary serach on left
+                root = root.left;
+            } else {		//binary search on right
+                root = root.right;
+            }
+        }
+        return closestVal;
+    }
+}
+
+FIX TO HANDLE PRINTING SMALLEST IF DIFFERENCE IS THE SAME
+
+class Solution {
+    public int closestValue(TreeNode root, double target) {
+        int val = root.val;
+        int closest = root.val; 
+        while(root!=null){
+            val = root.val;
+            if(Math.abs(target - val) < Math.abs(target-closest)){
+                closest=val;
+            } else if(Math.abs(target - val) == Math.abs(target-closest) && val < closest){
+                closest=val;
+            }
+            if(root.val > target){
+                root=root.left;
+            } else {
+                root=root.right;
+            }
+
+        }
+        return closest;
+    }
+}
@@ -0,0 +1,55 @@
+Pair<TreeNode, Integer> p = new Pair<>();
+key = p.getKey();
+value = p.getValue();
+
+Collections.sort(toSort, (a,b)->b-a); 
+Collections.reverse(array);
+
+double total = 10; 
+Math.random()*total 
+
+HashMap<Integer, Integer> map = new HashMap<>();
+map.getOrDefault(i, 0);
+for(int x: map.keySet()){
+}
+
+String s = "arman khondker"
+String [] sa = s.split("a") //[rm, n khondker]
+
+Deque<Integer> q = new ArrayDeque<>(); //can be used as both a stack and a queue
+q.removeFirst() //removes the first element
+q.removeLast(); removes the  last element
+q.pollFirst();
+q.pollLast();
+*** q.poll() //it treats as queue (not a stack) and polls the first element!
+
+String Concatenation
+one line concatenation with "+" and StringBuilder.append() generate exactly the same bytecode.
+exceptions :
+multithreaded environment : StringBuffer
+concatenation inside of loops : StringBuilder/StringBuffer
+
+int[][] dirs = new int[]{{-1,0}, {1, 0}, {0, 1}, {0,-1}}       
+
+throw new IllegalArgumentException("Invalid input as p and q are guaranteed to exist");
+
+String [] split = path.split("/")
+
+
+if(arr[1].equals("start")) //STRING COMPARISON USE .equals
+
+Integer.parseInt(s); //to convert from STRING to int. valueOf(s) is used to convert to Integer
+
+
+
+Algorithms
+
+QuickSort (uses QuickSelect method, Java uses under the hood)
+TC: O(N) in average case, O(N^2) worst case when we select the pivot in bad position
+SC: O(logN) 
+
+Morris Traversal
+can traverse a tree in O(N) time
+
+Union Find
+an algorithm for finding connected components in a graph