class Solution {
    public int minPathSum(int[][] grid) {
        int[] dp = new int[grid[0].length];
        dp[0] = grid[0][0];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i - 1] + grid[0][i];
        }

        for (int i = 1; i < grid.length; i++) {
            dp[0] = dp[0] + grid[i][0];
            for (int j = 1; j < dp.length; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        return dp[dp.length - 1];
    }
}

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // Edge case
        if (head == null || head.next == null)
            return head;

        // Count how many nodes in the given list
        int count = 1;
        ListNode ptr = head;
        // When the loop ends, ptr stores the last node
        while (ptr.next != null) {
            count += 1;
            ptr = ptr.next;
        }

        // Equavilent shift
        k %= count;

        // If the shift step is 0, then return
        if (k == 0)
            return head;

        ListNode newEnd = head;
        for (int i = 0; i < count - k - 1; i++) {
            newEnd = newEnd.next;
        }

        ListNode newHead = newEnd.next;
        newEnd.next = null;
        ptr.next = head;
        return newHead;
    }
}

class Solution {
    public void rotate(int[][] matrix) {
        int left = 0, right = matrix[0].length - 1, up = 0, down = matrix.length - 1;
        while (left < right) {
            for (int i = left; i < right; i++) {
                // element in row up.
                int temp = matrix[up][i];
                // row up to col right
                temp = swap(matrix, temp, i - left + up, right);
                // col right to row down
                temp = swap(matrix, temp, down, right - (i - left));
                // row down to col left
                temp = swap(matrix, temp, down - (i - left), left);
                // col left to row up
                temp = swap(matrix, temp, up, i);
            }
            left += 1;
            right -= 1;
            up += 1;
            down -= 1;
        }
    }

    private int swap(int[][] matrix, int tmp, int row, int col) {
        int temp = matrix[row][col];
        matrix[row][col] = tmp;
        return temp;
    }
}

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, 0, nums);
        return ans;
    }

    private void helper(List<List<Integer>> ans, int pos, int[] nums) {
        if (pos == nums.length) {
            ans.add(arrayToList(nums));
            return;
        }
        Set<Integer> visited = new HashSet<>();
        for (int i = pos; i < nums.length; i++) {
            if (visited.add(nums[i])) {
                swap(nums, pos, i);
                helper(ans, pos + 1, nums);
                swap(nums, pos, i);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private List<Integer> arrayToList(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        for (int num : nums) {
            ans.add(num);
        }
        return ans;
    }
}

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1)
            return 0;
        int currMaxReach = 0, farthest = 0, jumps = 0;
        for (int i = 0; i < nums.length; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currMaxReach) {
                jumps += 1;
                currMaxReach = farthest;
                if (currMaxReach >= nums.length - 1)
                    return jumps;
            }
        }
        return jumps;
    }
}

class Solution {
    public int trap(int[] height) {
        if (height.length == 0) {
            return 0;
        }
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, ans = 0;
        while (left <= right) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
                left += 1;
                continue;
            }
            if (height[right] >= rightMax) {
                rightMax = height[right];
                right -= 1;
                continue;
            }
            if (leftMax <= rightMax) {
                ans += leftMax - height[left];
                left += 1;
            } else {
                ans += rightMax - height[right];
                right -= 1;
            }
        }
        return ans;
    }
}

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int currSum = nums[i] + nums[left] + nums[right];
                if (Math.abs(currSum - target) < Math.abs(ans - target)) {
                    ans = currSum;
                }
                if (currSum < target) {
                    left += 1;
                } else if (currSum > target) {
                    right -= 1;
                } else {
                    return currSum;
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int reverse(int x) {
        int ans = 0;
        while (x != 0) {
            int currentDigit = x % 10;
            if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && currentDigit > 7)) {
                return 0;
            }
            if (ans < Integer.MIN_VALUE / 10 || (ans == Integer.MIN_VALUE / 10 && currentDigit == -9)) {
                return 0;
            }
            ans = ans * 10 + currentDigit;
            x /= 10;
        }
        return ans;
    }
}

import java.util.*;

class Program {
    public static int[] mergeSort(int[] array) {
        int[] aux = array.clone();
        helper(array, aux, 0, array.length - 1);
        return array;
    }

    private static void helper(int[] main, int[] aux, int start, int end) {
        if (start == end) {
            return;
        }
        int middle = start + (end - start) / 2;
        helper(aux, main, start, middle);
        helper(aux, main, middle + 1, end);
        doMerge(main, aux, start, middle, end);
    }

    private static void doMerge(int[] main, int[] aux, int start, int middle, int end) {
        int ptrOne = start, ptrTwo = middle + 1, ptrMain = start;
        while (ptrOne <= middle && ptrTwo <= end) {
            if (aux[ptrOne] <= aux[ptrTwo]) {
                main[ptrMain] = aux[ptrOne];
                ptrOne += 1;
            } else {
                main[ptrMain] = aux[ptrTwo];
                ptrTwo += 1;
            }
            ptrMain += 1;
        }
        while (ptrOne <= middle) {
            main[ptrMain++] = aux[ptrOne++];
        }
        while (ptrTwo <= end) {
            main[ptrMain++] = aux[ptrTwo++];
        }
    }
}

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        int length = heights.length;
        for (int i = 0; i < length; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }
}