Table of Contents
O(n1+n2) recursive stack space, where n1-length of LL1 and n2-length of LL2 Obviously, for both recursive and iterative, it’s O(N+M) where N and M are lengths of the 2 linked lists
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//recursively
//make the next node of the smaller one to be the result after calling the recursive method
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val <= list2.val){
list1.next = mergeTwoLists (list1.next, list2);
return list1;
}else{
list2.next = mergeTwoLists (list1, list2.next);
return list2;
}
}
}
//iteratively
if (list1 == null) return list2;
if (list2 == null) return list1;
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
curr.next = list1;
list1 = list1.next;
}else{
curr.next = list2;
list2 = list2.next;
}
curr = curr.next;
}
curr.next = list1 == null ? list2 : list1;
return dummy.next;
when we are processing the right parenthesis, if the stack is empty, which means there is nothing to pop, smth doesn’t really match, then return false; Or if the top one on the stack is not the corressponding left parenthese, we also return false
return stack.isEmpty();class Solution {
public boolean isValid(String s) {
//({[])}]
Stack<Character> stack = new Stack<>();
for(Character c: s.toCharArray()){
if ( c == '{') stack.push('}');
else if (c == '[') stack.push (']');
else if (c == '(') stack.push(')');
else{//c is the right part
if(stack.isEmpty() || stack.pop() != c) return false;
}
}
return stack.isEmpty();
}
}
Given a string that consists of brackets, write a function bracketMatch that takes a bracket string as an input and returns the minimum number of brackets you’d need to add to the input in order to make it correctly matched. Examples:
input: text = “(()”
output: 1
input: text = “(())”
output: 0
input: text = “())(”
output: 2
public static int bracketMatch(String text) {
int open = 0;
int close = 0;
for (int i = 0; i < text.length(); i ++){
if (str.charAt(i) == '('){
open ++;
}else{ // ")"
if (open > 0){
open --;
}else{
close ++;
}
}
}
return open + close;
}
public static int bracketMatch(String text) {
Stack<Character> stack = new Stack();
for(char c: text.toCharArray()){
if (c == '('){
stack.push('(');
}else{ // close bracket
if (stack.isEmpty() == false){
if (stack.peek() == '('){
stack.pop();
}else{
stack.push(')');
}
}else{
stack.push(')');
}
}
}
return stack.size();
}
Using a hashmap
class Solution {
public int[] twoSum(int[] nums, int target) {
//make a hashmap with key as the integer, value as its difference with the target. and we loop through the hashmap, to check if the corressponding value is within the nums array.
int[] ans = new int[2];
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
if (map.containsKey(target-nums[i])){
ans[1] = i;
ans[0] = map.get(target-nums[i]);
return ans;
}
map.put(nums[i], i);
}
return ans;
}
}
class Solution {
//Time complexity: x.length() /2
// Space: constant
public boolean isPalindrome(int x) {
String s = String.valueOf(x);
int left = 0, right = s.length() - 1;
while (left <= right){
if (s.charAt(left) != s.charAt(right)) return false;
left ++;
right --;
}
return true;
}
}
Time complexity: max (26, s.length(), t.length)
Space complexity: 26*2 = 52
class Solution {
public boolean isAnagram(String s, String t) {
int[] astore = new int[26];
int[] bstore = new int[26];
for(char c: s.toCharArray()){
astore[c - 'a'] ++;
}
for(char c: t.toCharArray()){
bstore[c - 'a']++;
}
for(int i = 0; i < 26; i ++){
if (astore[i] != bstore[i]){
return false;
}
}
return true;
}
}
Note that to get the index of the first unique string, we need to loop through s, not the hashmap.
class Solution {
public int firstUniqChar(String s) {
HashMap<Character, Integer> map = new HashMap<>();
for(char c: s.toCharArray()){
if(map.containsKey(c)){
map.put(c, map.get(c) + 1);
}else{
map.put(c, 1);
}
}
for(int i = 0; i < s.length(); i ++){
if (map.get(s.charAt(i)) == 1){
return i;
}
}
return -1;
}
}
public int firstUniqChar(String s) {
int[] freq = new int[26];
for(char c: s.toCharArray()){
freq[c - 'a'] ++;
}
for(int i = 0; i < s.length(); i ++){
if (freq[s.charAt(i)-'a'] == 1){
return i;
}
}
return -1;
}
Intersection: keep track of what we already have seen keep track one of the list, then go to the other list to see if we have seen it before
Throw one list into a hashset, record it is b1, b2, in our hashset
Time: O(m+n) Space: visited allocated, O(min(m,n)) O(n) in general
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> visited = new HashSet<>();
while(headA != null){
visited.add(headA);
headA = headA.next;
}
while (headB != null){
if (visited.contains(headB)){
return headB;
}
headB = headB.next;
}
return null;
}
}
“hey nodeB I will chase you till the day I meet you”
Time: O(m+n) Space: constant
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pointerA = headA;
ListNode pointerB = headB;
while (pointerA != pointerB){
if(pointerA == null){
pointerA = headA;
}else{
pointerA = pointerA.next;
}
if(pointerB == null){
pointerB = headB;
}else{
pointerB = pointerB.next;
}
}
return pointerA;
}
Approach 3:
Calcualte length, wait for the shorter to catch up, and get the intersection
DFS, recursions
one gets added to the string, left node gets passed in if it’s not null, right same logic. Time: O(n) Space: O(n)
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> ans = new ArrayList<>();
if(root == null) return ans;
String currpath = Integer.toString(root.val);
if(root.left == null && root.right == null){
ans.add(currpath);
}
if(root.left != null){
dfs(root.left, currpath, ans);
}
if(root.right != null){
dfs(root.right, currpath, ans);
}
return ans;
}
public void dfs(TreeNode root, String currpath, List<String> list){
currpath += "->" +root.val;
if (root.left == null && root.right == null){
list.add(currpath);
return;
}
if(root.left != null){
dfs(root.left, currpath, list);
}
if(root.right != null){
dfs(root.right, currpath, list);
}
}
}
class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {
stack = new Stack();
minStack = new Stack();
}
public void push(int val) {
if(minStack.isEmpty() || val <= minStack.peek()){
minStack.push(val);
}
stack.push(val);
}
public void pop() {
if(minStack.peek().equals(stack.peek())) minStack.pop();
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
Each node stores 2 ints, val and min. There are N nodes, thus 2N. vs other solutions N+K memory complexity, where K is when min needs to be stored.
Need to see that we are getting the minimum between the current value and head’s minimum. And we are setting the previous head to the next.
class MinStack {
private Node head;
public MinStack() {
this.head = head;
}
public void push(int val) {
if (head == null){
head = new Node(val, val, null);
}else{
head = new Node(val, Math.min(head.min, val), head);
}
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
private class Node {
int val;
int min;
Node next;
private Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}
Since stack is a FILO data structure, we only need to push everything onto it, and then pop them one by one and chain them together into a new LinkedList.
public ListNode reverseList(ListNode head) {
//prev, node, node.next
//traverse the linkedlist, put into the stack
Stack<ListNode> stack = new Stack<>();
while (head != null){
stack.push(head);
head = head.next;
}
ListNode dumm = new ListNode(-1);
head = dumm;
while (stack.isEmpty() == false){
ListNode curr = stack.pop();
head.next = new ListNode(curr.val);
head = head.next;
}
return dumm.next;
}
Make a newhead.
First store the value of head.next into ListNode next
Make head points to the newHead
turn newHead into head, then turn head into the next. So it will become the next pointing to the head
Note: Note that if we switch and make turning head into next first, then next will point to newhead, it will fail.
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
while (head != null){
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}
class Solution {
public ListNode reverseList(ListNode head) {
return reverseList(head, null);
}
private ListNode reverseList(ListNode head, ListNode newHead){
if(head == null) return newHead;
ListNode next = head.next;
head.next = newHead;
return reverseList(next, head);
}
}
first, skip the head whenever it starts with nodes as same value as val
- Next, we make a current node pointing at head
- while the curr and curr.next are not null,
- if the curr.next.val is same as val, we skip it by
curr.next = curr.next.next;- else we just do curr = curr.next as normal traversals
- return
headultimately
public ListNode removeElements(ListNode head, int val) {
while (head != null && head.val == val){
head = head.next;
}
ListNode curr = head;
while (curr != null && curr.next != null){
if (curr.next.val == val){
curr.next = curr.next.next;
}else{
curr = curr.next;
}
}
return head;
}
> Keep a res as a characters stack.
> Iterate characters of S one by one.
> If the next character is same as the last character in res,
> pop the last character from res.
> In this way, we remove a pair of adjacent duplicates characters.
> If the next character is different, we append it to the end of res
public String removeDuplicates(String s) {
StringBuilder ans = new StringBuilder();
for(char c: s.toCharArray()){
if (ans.length() > 0 && ans.charAt(ans.length() - 1) == c){
ans.deleteCharAt(ans.length() - 1); // O(n)
}else{
ans.append(c); //O(1)
}
}
return ans.toString();
}
i refers to the index to set next character in the output string. j refers to the index of current iteration in the input string.
Iterate characters of S one by one by increasing j.
If S[j] is same as the current last character S[i - 1],
we remove duplicates by doing i -= 2.
If S[j] is different as the current last character S[i - 1], we set S[i] = S[j] and increment i++.
##
##
##
##
##
##
##
##
##
##