Misc Problems

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

class Solution {
    //You are given two integer arrays nums1 and nums2,
    // sorted in non-decreasing order, and two integers m and n,
    // representing the number of elements in nums1 and nums2 respectively.
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int l1 = m - 1;
        int l2 = n - 1;
        int i = l1 + l2 + 1;
        while (l1 >= 0 && l2 >= 0) {
            if (nums1[l1] > nums2[l2]) {
                nums1[i--] = nums1[l1--];
            } else {
                nums1[i--] = nums2[l2--];
            }
        }
        while (l2 >= 0) {
            nums1[i--] = nums2[l2--];
        }
    }

    //Given an integer array nums and an integer val, remove all occurrences of val in nums in-place.
    // The order of the elements may be changed.
    // Then return the number of elements in nums which are not equal to val.
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int index = n - 1;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == val) {
                while (index >= 0) {
                    if (nums[index] == val) {
                        nums[index] = Integer.MAX_VALUE;
                        index--;
                    } else if (nums[i] != Integer.MAX_VALUE) {
                        nums[i] = nums[index];
                        nums[index] = Integer.MAX_VALUE;
                        index--;
                        break;
                    } else {
                        index--;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != Integer.MAX_VALUE) {
                count++;
            }
        }
        return count;
    }
    //Given an integer array nums sorted in non-decreasing order,
    // remove the duplicates in-place such that each unique element appears only once.
    // The relative order of the elements should be kept the same.
    // Then return the number of unique elements in nums.

    public int removeDuplicates(int[] nums) {
        int inderpos = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[inderpos++] = nums[i];
            }
        }
        for (int j = inderpos; j < nums.length; j++) {
            nums[j] = 0;
        }

        return inderpos;
    }

    //Given an integer array nums sorted in non-decreasing order,
    // remove some duplicates in-place such that each unique element appears at most twice.
    // The relative order of the elements should be kept the same.
    //
    //Since it is impossible to change the length of the array in some languages,
    // you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
    public int removeDuplicatesV2(int[] nums) {
        int inderpos = 1;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[inderpos++] = nums[i];
                count = 1;
            } else if (nums[i] == nums[i - 1] && count < 2) {
                count++;
                nums[inderpos++] = nums[i];
            }
        }
        for (int j = inderpos; j < nums.length; j++) {
            nums[j] = 0;
        }
        return inderpos;
    }

    //Given an array nums of size n, return the majority element.
    //
    //The majority element is the element that appears more than ⌊n / 2⌋ times.
    // You may assume that the majority element always exists in the array.
    public int majorityElement(int[] nums) {
        int votes = 0;
        int candidate = -1;

        for (int i = 0; i < nums.length; i++) {
            if (votes == 0) {
                candidate = nums[i];
            }
            if (nums[i] == candidate) {
                votes++;
            } else {
                votes--;
            }
        }
        return candidate;
    }

    //Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = 0;

        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = nums[start];

            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }

    //You are given an array prices where prices[i] is the price of a given stock on the ith day.
    //
    //You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
    //
    //Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }

        return maxProfit;
    }

    //You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
    //
    //On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
    //
    //Find and return the maximum profit you can achieve.
    public int maxProfitV2(int[] prices) {
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i - 1] < prices[i]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }

        return maxProfit;
    }

    //You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
    //
    //Return true if you can reach the last index, or false otherwise.
    public boolean canJump(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > max) {
                return false;
            }
            max = Math.max(max, i + nums[i]);
        }

        return true;
    }

    //ou are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
    //
    //Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j]
    public int jump(int[] nums) {
        int jumps = 0;

        int fartherest = 0;
        int currentIndex = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            fartherest = Math.max(fartherest, i + nums[i]);
            if (i == currentIndex) {
                jumps++;
                currentIndex = fartherest;
            }
        }
        return jumps;
    }

    //Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.
    //
    //According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
    //
    //
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;

        for (int i = 0; i < n; i++) {
            int h = n - i;
            if (citations[i] >= h) {
                return h;
            }
        }

        return 0;
    }

    //Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
    //
    //The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
    //
    //You must write an algorithm that runs in O(n) time and without using the division operation.
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;

        int[] answer = new int[length];
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }
        int rightProduct = 1;
        for (int i = length - 1; i >= 0; i--) {
            answer[i] = answer[i] * rightProduct;
            rightProduct = rightProduct * nums[i];
        }
        return answer;
    }

    //There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
    //
    //You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
    //
    //Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalTank = 0;
        int currentTank = 0;
        int startStation = 0;
        for (int i = 0; i < gas.length; i++) {
            totalTank += gas[i] - cost[i];
            currentTank += gas[i] - cost[i];

            if (currentTank < 0) {
                currentTank = 0;
                startStation = i + 1;
            }

        }
        return totalTank >= 0 ? startStation : -1;
    }

    //There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
    //
    //You are giving candies to these children subjected to the following requirements:
    //
    //Each child must have at least one candy.
    //Children with a higher rating get more candies than their neighbors.
    public int candy(int[] ratings) {

        int n = ratings.length;
        int[] candies = new int[n];


        for (int i = 0; i < n; i++) {
            candies[i] = 1;
        }


        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }


        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }

        return totalCandies;
    }
    //Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

    public int trap(int[] height) {
        int n = height.length;
        int trappedWater = 0;
        int leftMax = height[0];
        int rightMax = height[n - 1];
        int left = 1;
        int right = n - 2;

        while (left <= right) {
            if (leftMax >= rightMax) {
                trappedWater += Math.max(0, rightMax - height[right]);
                rightMax = Math.max(rightMax, height[right]);
                right--;

            } else {
                trappedWater += Math.max(0, leftMax - height[left]);
                leftMax = Math.max(leftMax, height[left]);
                left++;
            }
        }
        return trappedWater;
    }

    //Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
    //
    //Symbol       Value
    //I             1
    //V             5
    //X             10
    //L             50
    //C             100
    //D             500
    //M             1000
    public int romanToInt(String s) {
        java.util.Map<Character, Integer> romanMap = new java.util.HashMap<>();
        romanMap.put('I', 1);
        romanMap.put('V', 5);
        romanMap.put('X', 10);
        romanMap.put('L', 50);
        romanMap.put('C', 100);
        romanMap.put('D', 500);
        romanMap.put('M', 1000);

        int result = 0;
        int prevValue = 0;


        for (int i = s.length() - 1; i >= 0; i--) {
            int currentValue = romanMap.get(s.charAt(i));
            if (currentValue < prevValue) {
                result -= currentValue;
            } else {
                result += currentValue;
            }
            prevValue = currentValue;
        }

        return result;
    }

    //Given an integer, convert it to a Roman numeral.
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(symbols[i]);
            }

        }
        return sb.toString();
    }

    //Given a string s consisting of words and spaces, return the length of the last word in the string.
    //
    //A word is a maximal substring consisting of non-space characters only.
    public int lengthOfLastWord(String s) {
        int length = 0;
        int i = s.length() - 1;


        while (i >= 0 && s.charAt(i) == ' ') {
            i--;
        }


        while (i >= 0 && s.charAt(i) != ' ') {
            length++;
            i--;
        }

        return length;
    }

    //Write a function to find the longest common prefix string amongst an array of strings.
    //
    //If there is no common prefix, return an empty string "".
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String pref = strs[0];

        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(pref) != 0) {
                pref = pref.substring(0, pref.length() - 1);
                if (pref.isEmpty()) {
                    return "";
                }
            }
        }

        return pref;
    }

    //Given an input string s, reverse the order of the words.
    //
    //A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
    //
    //Return a string of the words in reverse order concatenated by a single space.
    public String reverseWords(String s) {
        StringBuilder result = new StringBuilder();
        int i = s.length() - 1;

        while (i >= 0) {

            while (i >= 0 && s.charAt(i) == ' ') {
                i--;
            }
            if (i < 0) break;

            int end = i;

            // Find the start of the word
            while (i >= 0 && s.charAt(i) != ' ') {
                i--;
            }
            int start = i + 1;


            result.append(s.substring(start, end + 1));
            result.append(" ");
        }


        return result.toString().trim();
    }

    //The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
    public String convert(String s, int numRows) {
        int length = s.length();
        if (length <= numRows || numRows == 1) {
            return s;
        }

        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }
        int currentRow = 0;
        boolean goingDown = false;
        for (char c : s.toCharArray()) {
            rows[currentRow].append(c);
            if (currentRow == 0 || currentRow == numRows - 1) {
                goingDown = !goingDown;
            }
            if (goingDown) {
                currentRow++;
            } else {
                currentRow--;
            }
        }

        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }

        return result.toString();
    }

    //Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) {
            return -1;
        }
        if (needle.length() == 0) {
            return -1;
        }

        int l1 = haystack.length();
        int l2 = needle.length();

        for (int i = 0; i <= l1 - l2; i++) {
            if (haystack.substring(i, i + l2).equalsIgnoreCase(needle)) {
                return i;
            }
        }

        return -1;
    }

    //A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 1) {
            return true;
        }
        StringBuilder sb = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                sb.append(Character.toLowerCase(c));
            }
        }
        String s1 = sb.toString();

        int left = 0, right = s1.length() - 1;
        System.out.println(s1);
        while (left < right) {
            if (s1.charAt(left) != s1.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }

    //Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
    //
    //A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;

        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }

        return i == s.length();
    }

    //Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 1) {
            return null;
        }
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            }
            if (sum > target) {
                right--;
            }
            if (sum < target) {
                left++;
            }
        }


        return null;
    }

    //You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
//
//Find two lines that together with the x-axis form a container, such that the container contains the most water.
//
//Return the maximum amount of water a container can store.
    public int maxArea(int[] height) {


        int water = 0;
        int left = 0;
        int right = height.length - 1;

        while (left < right) {
            int currentWater = Math.min(height[right], height[left]) * (right - left);
            water = Math.max(currentWater, water);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }

        }
        return water;
    }

    //Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
//
//Notice that the solution set must not contain duplicate triplets.
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);

        int length = nums.length;
        for (int i = 0; i < length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }

            }

        }
        return list;
    }

    //Given an array of positive integers nums and a positive integer target,
    // return the minimal length of a subarray whose sum is greater than or equal to target.
    // If there is no such subarray, return 0 instead.
    public int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            if (nums[0] >= target) {
                return 1;
            }
        }


        int ans = Integer.MAX_VALUE;
        int sum = 0;
        int start = 0;


        for (int end = 0; end < nums.length; end++) {
            sum += nums[end];
            while (sum >= target) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
        }


        if (ans == Integer.MAX_VALUE) return 0;
        return ans;
    }

    //Given a string s, find the length of the longest substring without duplicate characters.
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        int left = 0;
        int right = 0;

        HashMap<Integer, Boolean> vMap = new HashMap();

        int maxWindow = 1;
        while (right < s.length()) {
            while (vMap.get(s.charAt(right) - 'a') != null && vMap.get(s.charAt(right) - 'a') == true) {
                int i = s.charAt(left) - 'a';
                vMap.put(i, false);
                left++;
            }
            vMap.put(s.charAt(right) - 'a', true);

            maxWindow = Math.max(right - left + 1, maxWindow);
            right++;
        }
        return maxWindow;
    }


    public static void main(String[] args) {

        Solution s = new Solution();
        int length = s.lengthOfLongestSubstring("au");
        System.out.println(length);
    }

    private static void printArray(int[] result) {
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }
    }
}