/*  Given a binary tree, return the inorder, preorder, postorder traversal of its nodes values

Input: [1,null,2,3]
   1
    \
     2
    /
   3    */

//inorder - Output: [1,3,2]     order is (Left, Root, Right)

public void inorder(TreeNode root,List list) {
  if(root == null) return;
  inorder(root.left, list);
  list.add(root.val);
  inorder(root.right, list);
}

public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  if (root==null) return res;

  Stack<TreeNode> stack = new Stack<>();
  TreeNode curr = root;

  while(curr != null || !stack.isEmpty()){
    while (curr!=null){
        stack.push(curr);
        curr=curr.left;
    }
    curr=stack.pop();
    res.add(curr.val);
    curr=curr.right;
  }
  return res;
}

/**

        10           #1      #2     #3      #4      #5
       /  \         ------  ------  ------  ------  ------
     11    18       | 15 |  |    |  |    |  |    |  |    |
    /  \            ------  ------  ------  ------  ------
  15    12          | 11 |  | 12 |  |    |  |    |  |    |
                    ------  ------  ------  ------  ------
                    | 10 |  | 10 |  |    |  | 18 |  | 18 |
                    ------  ------  ------  ------  ------
#1 push root to stack
then we traverse to left node, because left node is not null then we push the node into stack
push 11 then repeat and push 15.

#2 -> because 15 doesnt have any nodes we pop 15 out and print it or push to list
then we go to the right node of 11. node 11 doesn't have more node on the right
so we pop 11 out and print it. Then we traverse to the right node.
because the right node is not null then we add it to stack

#3 -> because theres no more child from 12 then we go to the root node which is 10
theres no more left child of 10 so we pop it and print

#4 -> We push 18 into stack now because root doesnt have anymore child on the left.

#5 -> we check the left and there are no more child so we pop it out of the stack and print

result = [15, 11, 12, 10, 18]

*/


//PreOrder - Output: [1,2,3]    order is (Root, Left, Right)

public void preorder(TreeNode root, List list) {
  if(root == null) {
      return;
  }
  list.add(root.val);
  preorder(root.left,list);
  preorder(root.right, list);
}

public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> list = new ArrayList<>();
  if(root == null) return list;
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);
  while(!stack.isEmpty()) {
    TreeNode current = stack.pop();
    list.add(current.val);
    if(current.right!=null) {
       stack.push(current.right);
    }
    if(current.left!=null) {
      stack.push(current.left);
    }
  }
  return list;
}

/**

        10           #1      #2     #3      #4      #5      #6      #7
       /  \         ------  ------  ------  ------  ------  ------  ------
     11    18       |    |  |    |  |    |  |    |  | 15 |  |    |  |    |
    /  \            ------  ------  ------  ------  ------  ------  ------
  15    12          |    |  |    |  | 11 |  |    |  | 12 |  | 12 |  | 12 |
                    ------  ------  ------  ------  ------  ------  ------
                    | 10 |  |    |  | 18 |  | 18 |  | 18 |  | 18 |  | 18 |
                    ------  ------  ------  ------  ------  ------  ------

#1 -> add in root
#2 -> enter loop and pop element out, can either print or add to list
#3 -> after element has been popped out, check if element has child. If it does then add
right child then leftroot has 2 child so add in right child of 18 then left child of 11
#4 -> pop out 11 and check if it has children
#5 -> 11 has children, so add in right (12) then left (15)
#6 -> pop out 15, but has no child so we run through the loop again
#7 -> pop out 12, but has no child so we run through the loop again

18 is the last element, also no child so pop it, then print it

if all elements were added to a list, then traverse through the list and print

result = [10, 11, 15, 12, 18]
*/

//PostOrder - Output: [3,2,1]   order is (Left, Right, Root)

public void postOrder(TreeNode root, List list) {
  if(root == null) return;
  postOrder(root.left, list);
  postOrder(root.right, list);
  list.add(root.val);
}

public List<Integer> postorderTraversal(TreeNode root) {
  List<Integer> list = new ArrayList<>();
  if(root == null) return list;
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);
  while(!stack.isEmpty()) {
    TreeNode curr = stack.pop();
    list.add(0,curr.val);
    if(curr.left!=null) {
      stack.push(curr.left);
    }
    if(curr.right!=null) {
       stack.push(curr.right);
    }
  }
  return list;
}
/**

        10           #1      #2     #3      #4      #5      #6      #7      #8
       /  \         ------  ------  ------  ------  ------  ------  ------  ------
     11    18       | 15 |  |    |  | 12  | |    |  |    |  |    |  |    |  |    |
    /  \            ------  ------  ------  ------  ------  ------  ------  ------
  15    12          | 11 |  | 11 |  | 11 |  | 11 |  | 11 |  |    |  | 18 |  |    |
                    ------  ------  ------  ------  ------  ------  ------  ------
                    | 10 |  | 10 |  | 10 |  | 10 |  | 10 |  | 10 |  | 10 |  | 10 |
                    ------  ------  ------  ------  ------  ------  ------  ------

#1 -> push root into stack, set the pointer of root to point to the next left node.
if left node (11) exists then add 11 to the stack
check if next left node(15) is empty or not, because the node exists then again push 15
into the stackcheck if next left node is empty, because it is empty check
check the top element's child of the right tree using stack peek method,
Or pop out the element and add it to array or print if no right child exists

#2 -> 15 has no more child node, so we pop out 15 then we check if 11 has any right child
#3 -> 11 has a right child so we push 12 into stack and repeat #1
#4 -> 12 has no more child so we pop 12 then check 11
#5 -> 11 has no more child so we pop 11 out
#6 -> check if 10 has a right child
#7 -> 10 has a right child so we push the child into the stack
#8 -> check if 18 has left child, because there is none, so we check the right child
which is also none, pop 18 out of the stack
#9 -> 10 has no more child so we pop it out of the stack and then print


result = [15, 12, 11, 18, 10]

*/

//Level order traversal

public void levelOrder (Node root) {
    Queue<Node> q = new Queue<>();
    q.add(root);

    while(!q.isEmpty()) {
        Node temp = q.poll; //removes the element at the front
        if(temp.left != null) {
            q.add(temp.left);
        }
        if(temp.right != null) {
            q.add(root.right);
        }
    }
}

/*
N-ary Tree Postorder Traversal

Given an n-ary tree, return the postorder traversal of its nodes values.

    1
  / | \
 3  2  4
/ \
5  6

Return its postorder traversal as: [5,6,3,2,4,1].

post order is left, right then root
*/

public List<Integer> postorder(Node root) {
    List<Integer> ls = new ArrayList<>();
    if(root == null) {
        return ls;
    }

    for(Node child: root.children) {   //add all the children in first
        ls.addAll(postorder(child));
    }
    ls.add(root.val);   //once all children is added, then you add the root
    return ls;
}

/*
Given an n-ary tree, return the preorder traversal of its nodes' values.

Return its preorder traversal as: [1,3,5,6,2,4].

preorder is root, then left, then right  */

public List<Integer> preorder(Node root) {
    List<Integer> ls = new ArrayList<>();
    if(root == null) {
        return ls;
    }
    ls.add(root.val);       //add in root first
    for(Node child: root.children) {
        ls.addAll(preorder(child));   //then add in the children
    }
    return ls;

}

//calculating height of a binary tree

int height(Node root) {
    if(root == null) {
        return -1
    }
    return 1 + Math.max(height(root.left), height(root.right))
}

/*
calculating size of a tree(number of nodes)
traverse through tree using any tree traversal methods andadd the item in a data structure
calculate size from arraylist and return number
*/
class solution {

    public static void inOrder(Node root,List list) {
        if(root == null) {
            return;
        }
        inOrder(root.left, list);
        list.add(root);
        inOrder(root.right, list);
    }

    public static int count(Node root) {
        List<Integer> ls = new ArrayList<>();
        inOrder(root, ls);
        int count = ls.size();
        return count
    }
}

or

//recursive method will recursively count all nodes on left and right.
public static int count(Node root) {
    if(root == null) {
        return 0;
    }
    return 1 + count(root.left) + count(root.right);
}

//check if binary tree is BST

 public boolean isBST(TreeNode node, long lower_limit, long upper_limit) {
    if (node == null) {
        return true;
    }
    if (node.val <= lower_limit || upper_limit <= node.val) {
        return false;
    }
    return isBST(node.left, lower_limit, node.val) && isBST(node.right, node.val, upper_limit);
}

public boolean isValidBST(TreeNode root) {
    return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE);

}

//binary search tree search and insert

public Node search(Node current, int val) {
    if(current == null) {
        return current;
    }
    if(current.val > val) { //if current value is greater than the value, check left
        return search(current.left, val);
    } //otherwise check right
    return search(current.right, val);

public Node addNode(Node current, int val) {
    if(current == null) {
        return new Node(val);   //if the root of tree does not exist, add a new node
    }
    if(val < current.val) { //if value is less than root or node, then it must go to left
        current.left = addNode(current.left, val);
    } else if(val > current.val) { //if value is more than root or node, then it must go to right
        current.right = addNode(current.right, val);
    } else {
        return current;
    }
    return current;
}

/*
construct binary search tree from its given level order traversal
*/
// function to get a new node
public static Node getNode(int data) {
    // Allocate memory
    Node newNode = new Node();

    // put in the data
    newNode.data = data;
    newNode.left = newNode.right = null;  //left and right node are null
    return newNode;
}
public Node LevelOrder(Node root , int data)
{
    if(root == null)
    {
        root = getNode(data);
        return root;
    }
    if(data <= root.data)
        root.left = LevelOrder(root.left, data);
    else
        root.right = LevelOrder(root.right, data);
    return root;
}

/*
Given a Binary Search Tree (BST) with the root node root,
return the minimum difference between the values of any two different nodes in the tree.

Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4
        /   \
      2      6
     / \
    1   3

while the minimum difference in this tree is 1, it occurs between node 1 and node 2,
also between node 3 and node 2.
*/

Integer prev;
int minDiff = Integer.MAX_VALUE;

public int minDiffInBST(TreeNode root) {
    inorder(root);
    return minDiff;
}

private void inorder(TreeNode root) {
    if (root == null)
        return;
    inorder(root.left);
    if (prev != null)
        minDiff = Math.min(minDiff, Math.abs(root.val - prev));
    prev = root.val;
    inorder(root.right);
}

/*

Lowest common Ancestor
Binary tree
Binary Search Tree

          4
        /   \
      2      6
     / \
    1   3

*/

public Node LCABT(Node root, Node n1, Node n2) {
    if(root == null) {
        return null;
    }
    if(root == n1 || root == n2) {
        return root;
    }
    Node left = LCABT(root.left, n1, n2);
    Node right = LCABT(root.right, n1, n2);

    if(left != null && right != null) {
        //left value or right value is returning not null so the value is near by
        return root;
    }
    if(left == null && right == null) {
        //left value and right value does not exist
        return null;
    }
    return left != null? left : right;
    //check left tree if value exist, traverse left, otherwise traverse right
}

public Node LCABsearchT(Node root, Node n1, Node n2) {
    if(root == null) {
        return null;
    }
    //if n1 and n2 is small than root, then traverse to left
    if(root.val > n1 && root.vale > n2) {
        return LCABsearchT(root.left, n1, n2);
    }
    //if n1 and n2 is bigger than root, then traverse to right
    if(root.val < n1 && root.val < n2) {
        return LCABsearchT(root.right, n1, n2);
    }
    return root;
}

/*
Test if binary tree is symmetric (mirror of itself)

need to check and compare left subtree and right subtree along with its children.
recursively check left and right and right and left child nodes
*/

public boolean isSymmetric(TreeNode root) {
    return root == null || check(leftTree, rightTree);
}

public boolean check(TreeNode leftTree, TreeNode rightTree) {
    if(leftTree == null && rightTree == null) {
        return true;
    }
    if(leftTree != null && rightTree != null) {
        return check(leftTree.right, rightTree.left) &&
            check(leftTree.left, rightTree.right);
    }
    return false;
}

//LINKEDLIST

public ListNode reverseList(ListNode head) {
    ListNode curr = head;
    ListNode prev = null;

    if(head == null) return prev;

    while(curr != null) {
        ListNode temp = curr.next; //pointer to point to next value
        curr.next = prev; //next value is point to previous value
        prev = curr; //previous is set to current number
        curr = temp; //current is set to next value
    }

    return prev;
}

/*
Merge two sorted linked lists and return it as a new list.
The new list should be made by splicing together the nodes of the first two lists.

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
*/

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode head = dummy;

    while(l1 != null && l2 != null) {
        //if l1 less than l2
        //add l1 to dummy and traverse l1
        //else add l2 to dummy and traverel2
        if(l1.val < l2.val) {
            head.next = l1;
            l1 = l1.next;
        } else {
            head.next = l2;
            l2 = l2.next;
        }
        head = head.next;
    }
    //most likely some sort of remainder in either list so we need to take account to that
    if(l1!=null) {
        head.next = l1;
    }
    if(l2!=null) {
        head.next = l2;
    }
    return dummy.next;
}

/*
Given a non-empty, singly linked list with head node head, return a middle node of linked list.
If there are two middle nodes, return the second middle node.

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

The number of nodes in the given list will be between 1 and 100.
*/

public ListNode middleNode(ListNode head) {
    ListNode l[] = new ListNode[100];
    int count = 0;

    while(head != null) {
        l[count++] = head; //count the amount of elements in linkedlist
        head = head.next; //traverse
    }
    return l[count/2];
}

/*
Given a sorted linked list, delete all duplicates such that each element appear only once.

Input: 1->1->2
Output: 1->2

Input: 1->1->2->3->3
Output: 1->2->3
*/

public ListNode deleteDuplicates(ListNode head) {
    ListNode curr = head;

    while(curr != null && curr.next != null) {
        if(curr.val == curr.next.val) {
            curr.next = curr.next.next;
        } else {
            curr = curr.next;
        }
    }
    return head;
}

/*
Given a singly linked list, determine if it is a palindrome.

Input: 1->2
Output: false

Input: 1->2->2->1
Output: true
*/

class Solution {
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while(head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }

    public boolean isPalindrome(ListNode head) {
        //have 2 pointers, one fast and one slow
        //slow pointer should reach to halfway of list
        //fast will reach to end + null
        //once fast is equal to null then we take slow and reverse it
        //set fast pointer back to head and traverse fast and slow
        //while slow doesnt hit null, if fast and slow is same then it is palindrome

        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        slow = reverse(slow); //reverse one half of the linked list
        fast = head; //set fast to point to head (first in list)
        while(slow != null) {
            if(fast.val != slow.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
}

/*
Sort a linked list in O(n log n) time using constant space complexity.

Input: 4->2->1->3
Output: 1->2->3->4

Input: -1->5->3->4->0
Output: -1->0->3->4->5

idea behind is merge sort
*/

public ListNode merge(ListNode l1, ListNode l2) {
    ListNode temp = new ListNode(0);
    ListNode curr = temp;

    while(l1 != null && l2 != null) {
        if(l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
    }
    if(l1 != null) {
        curr.next = l1;
        l1 = l1.next;
    }
    if(l2 != null) {
        curr.next = l2;
        l2 = l2.next;
    }
    return temp.next;
}

public ListNode sortList(ListNode head) {
    if(head == null || head.next == null) {
        return head;
    }
    ListNode temp = head;
    ListNode slow = head;
    ListNode fast = head;

    //idea is to have 2 pointers and traverse
    //split linkedlist into 2 lists
    //perform mergesort on linkedlist

    //head of list one is head, tail is temp
    //head of list two is slow, tail is fast
    while(fast != null && fast.next != null) {
        temp = slow; //temp will eventually be the tail of a linked list
        slow = slow.next; //slow will eventually be the head of a linkedlist
        fast = fast.next.next; //fast will eventually be tail of slow list
    }
    temp.next = null; //end of list one is now null
    ListNode leftSide = sortList(head); //split left linkedlist
    ListNode rightSide = sortList(slow); //split into right
    return merge(leftSide, rightSide);
}

/*
Merge k sorted linked lists and return it as one sorted list.
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

use a minheap, minheap implementation is using PQ and will sort itself.
*/

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        //for every node in lists
        for(ListNode head : lists) {
            // while the list is not empty
            while(head != null) {
                minHeap.add(head.val);
                head = head.next; //traverse list
            }
        }
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        while(!minHeap.isEmpty()) {
            head.next = new ListNode(minHeap.remove());
            head = head.next;
        }
    }
    return dummy.next;
}

/*
Given a singly linked list, group all odd nodes together followed by the even nodes.
Please note here we are talking about the node number and not the value in the nodes.

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
*/

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null) {
            return null;
        }

        //list will be odd first then even to the end of list
        //problem is split odd and even nodes, not the value it holds

        ListNode odd = head; //first index of list is odd
        ListNode even = head.next;//second index of list is even, point even to value after head
        ListNode evenHead = even; //head of even number

        while(even != null && even.next != null) {
            odd.next = even.next; //after all odd number, then even is next
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

/*
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 contain a single digit.
Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
*/

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //create new linkedlist to store result
    //traverse linkedlist
    //need variable to hold carry value

    ListNode dummy = new ListNode(0);
    ListNode l3 = dummy;
    int carry = 0;
    while(l1 != null && l2 != null) {
        int l1_val = (l1 != null)? l1.val : 0;
        //if one of the node is missing a value, fill it with 0
        int l2_val = (l2 != null)? l2.val : 0;
        //if one of the node is missing a value, fill it with 0
        int current_sum = l1.val + l2.val;
        carry = current_sum / 10; //calculate the carry
        int last_digit = current_sum % 10; //calculate the digit that is actually wanted

        // 2+5 = 7, carry = 0, digit = 7
        // 4+6 = 10 carry = 1, digit = 0

        ListNode new_node = new ListNode(last_digit);
        l3.next = new_node;

        if(l1 != null) {
            l1 = l1.next;
        }
        if(l2 != null) {
            l2 = l2.next;
        }
        l3 = l3.next;
    }
    if(carry > 0) {
        ListNode new_node = new ListNode(carry);
        l3.next = new_node.next;
        l3 = l3.next;
    }
    return dummy.next;
}

/*
ARRAY SORTING

Given an array with n objects colored red, white or blue,
sort them in-place so that objects of the same color are adjacent,
with the colors in the order red, white and blue.
use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library's sort function for this problem.

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
*/

class Solution {
    public void sortColors(int[] nums) {
        int count0 = 0;
        int count1 = 0;
        int count2 = 0;

        for(int i = 0; i < nums.length;i++) {
            if(nums[i] == 0) {
                count0++;
            }
            if(nums[i] == 1) {
                count1++;
            }
            if(nums[i] == 2) {
                count2++;
            }
        }

        for(int i = 0; i < nums.length; i++) {
            if(i < count0) {
                nums[i] = 0;
            } else if (i < count0 + count1) {
                nums[i] = 1;
            } else {
                nums[i] = 2;
            }
        }
    }
}

/*
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n)
to hold additional elements from nums2.

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]
*/

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int count = m + n -1;
    --m;
    --n;
    while(m >= 0 && n >= 0) {
        if(nums1[m] > nums2[n]) {  //compare element from both array
            nums1[count--] = nums1[m--];
            //if element in nums1 is bigger, move it to the back of array
        } else {
            nums1[count--] = nums2[n--];
            //if element in nums2 is bigger, move nums2 element to nums1 at the back
        }
    }
    while (n >= 0) {
        nums1[count--] = nums2[n--];
    }
}

/*
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
(i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit
Note that you cannot sell a stock before you buy one.

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
*/

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0) {
            return 0;
        }
        int buy = prices[0]; // set buy price to the first element
        int profit = 0 ;
        for(int i = 1; i < prices.length; i++) { //for each stock price
            if((prices[i] - buy) > 0) {
                //if each stock price minus that you bought is greater than 0
                profit = Math.max(prices[i] - buy, profit);
                //profit will be the comparison of the 2 profits
                //profit is the comparison of possible current profit vs the previous profits.
            } else {
                buy = prices[i];
            }
        }
        return profit;
    }
}

/*
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like
(i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time
(i.e., you must sell the stock before you buy again).

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
*/

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        //if a[i] < a[i+1] then the step would be to buy then sell
        //if a[i+1] is smaller then you traverse
        for(int i = 0; i < prices.length -1; i++) {
           if(prices[i] < prices[i+1]) {
               profit += prices[i+1] - prices[i];
            }
        }
        return profit;
    }
}

/*
Given an integer array nums, find the contiguous subarray (containing at least one number)
which has the largest sum and return its sum.

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
*/

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int tempSum = 0;

        for(int i = 0; i < nums.length; i++) { // go through array
            tempSum = tempSum + nums[i]; //keep adding number
            if(maxSum < tempSum) {
                maxSum = tempSum;
            }
            if(tempSum < 0) {
                tempSum = 0;
            }
        }
        return maxSum;
    }
}


/*
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.

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
*/

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for(int i : nums) {
        minHeap.add(i); //go through array and add element to minHeap
        if(minHeap.size() > k) {
            minHeap.remove(); //it will remove the smallest element in minheap
        }
    }
    return minHeap.remove();
}

STRINGS

/*
Reverse string by word
*/

public String reverseWord(String input) {
    String reverse = "";
    String wordSplit[] = input.split(" "); //assume word is separated by space
    for(int i = wordSplit.length -1; i > -1; i--) {
        reverse = reverse + wordSplit[i] + " ";
    }
    return reverse;
}
//original: I love java programming
//reversed: programming java love I

/*
Reverse string by character
*/

public String reverseCharWord(String input) {
    String reverse = "";
    String wordSplit = input.split(" "); //assume word is separated by space
    for(int i = input.length - 1; i < input.length -1; i--) {
        reverse = reverse + input.charAt(i);
    }
    return reverse;
}
//original: I love java programming
//reversed: gnimmargorp avaj evol I

public static HashSet<String> getAllPermutations(String str) {
    HashSet<String> permutations = new HashSet<>();

    if(str == null || str.length == 0) {
        permutations.add("");
        return permutations;
    }

    char first = str.substring(0); //first character is stored in variable
    String remainingString = str.substring(1); //the rest of the string minus first character
    //stored in remainingString variable
    HashSet<String> words = getAllPermutations(remainingString);
    for(String word : words) {
        for(int i = 0; i < word.length(); i++) {
            String prefix = word.substring(0, i);
            String suffix = word.substring(i);
            permutations.add(prefix + first + suffix);
        }
    }
    return permutations;
}

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

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Example 2:

Input: s = "rat", t = "car"
Output: false
*/

public boolean isAnagram(String s, String t) {
    if(s.length() != t.length()) {
        return false;
    } //check length, if length is not the same, then its not anagram
    char[] c1 = s.toCharArray(); //convert to character array
    char[] c2 = t.toCharArray(); //convert to character array
    Arrays.sort(c1); //sort character
    Arrays.sort(c2); //sort character
    String s1 = new String(c1); //create new string from sorted characters
    String s2 = new String(c2); //create new string from sorted characters
    if(s1.equals(s2)) { //if string1 is same as string2 then its anagram
        return true;
    }
        return false;
}

/*
Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[                           example where the
  ["ate","eat","tea"],              key  <-> value
  ["nat","tan"],                    aet       list[ate, eat, tea]
  ["bat"]
]
*/

//the anagrams all look alike when its sorted
//sort the word then some how group it, the sorted key word will be the key with a list of values
//using a map we can use the sorted word as a key
//value would be the unsorted word.
public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> anagramGroup = new ArrayList<>();
    HashMap<String, List<String>> map = new HashMap();

    for(String current : strs) {
        char[] characters = current.toCharArray();
        Arrays.sort(characters); //sort the current word
        String sorted = new String(chracters); //sorted word will become Key for map usage

        if(!map.containsKey(sorted)) { //if map does not contain key
            map.put(sorted, new ArrayList()); //add in the with a new arraylist
        }                       //MAP<KEY, LIST[,,,,]>
        map.get(sorted).add(current); //get the key and add current strings to list
    }
    anagramGroup.addAll(map.values()); //add all map values into list
    return anagramGroup;
}