arrays.java

/*
place two pointers at i = 0 & j = arr.length-1 while i < j
calculate prod & compare max , if arr[start] > arr[end]
end -= 1 else start += 1
O(N) runtime
O(1) space
*/
public int containerMostWater(int[] arr) {
    if arr.length < 2
        return -1;
    int start = 0;
    int end = arr.length - 1;
    int maxProd = 0
    while (start < end) {
        int prod = Math.min(arr[start], arr[end]) * (end - start);
        maxProd = Math.max(prod, maxProd);
        if (arr[start] > arr[end]) {
            end -= 1;
        }
        else {
            start += 1;
        }
    }
    return maxProd;
}

/*
set bestIndex = 0; for each element check nums[i]+index and compare with bestIndex
if bestIndex > i, then false
*/

public boolean canJump(int[] nums) {
    int maxIndex = 0;
    for (int i = 0; i < nums.length; i++){
        if (i > bestIndex) {
            return false;
        }
        bestIndex = max(bestIndex, nums[i] + i);
    }
    return true;
}




/*
initialize a stack then in a loop add each element to the stack
in a loop with condition stack and k and parseInt(stack[o]) > parseInt(i)
cur = 0
while(cur < stack.size and stack[cur] == '0': cur += 1

int newArray = stack.sublist(0, curr)

*/
public int[] removeKdigits(int[] nums. int k) {
    ArrayList<Int> holder = new ArrayList<Int>();
    for (String i : nums) {
        while(holder.size != 0 && k > 0 && parseInt(holder.get(0)) > parseInt(i)) {
            holder.remove(0)
            k--;
        }
        holder.add(i)
    }
    int cur = 0;
    while (cur < holder.size && holder[cur] == '0') {
        cur += 1;
    }
    holder = holder.sublist(0, cur);
    
    return holder;
}

/*
intialize maxSoFar & maxEnding

in a loop calculate maxEnding = maxEnding + a[i]
find maxSoFar = max(maxSoFar, maxEnding)
if maxEnding < 0: maxEnding = 0

*/

public int maxSubArraySum(int[] a) {
    int maxSoFar = 0;
    int maxEnding = 0;
    for (int i = 0; i < a.length; i++) {
        maxEnding = maxEnding + a[i];
        maxSoFar = Math.max(maxEnding, maxSoFar);
        if (maxEnding < 0) {
            maxEnding = 0;
        }
    }
    return maxSoFar;
}



/*
Sliding Window: intialize out = 0;
totalSum = 0; start -= 1;
in a loop add each element to totalSum
then in a while loop check if totalSum > target
totalSum = totalSum - arr[start]
start += 1;
out = out + i - start
*/

public int sumSubarrays(arr, target) {
    int out = 0;
    int totalSum = 0;
    int start = -1;
    for (int i : arr) {
        totalSum = totalSum + i;
        while (totalSum > target) {
            start++;
            totalSum = totalSum - arr[start];
        }
        out = out + i - start;
    }
    return out;
}

/*


place a pointer at i = 0, j = 1, if i == j , then length--
else i++, J++
*/

public int removeDuplicates(int[] nums) {
    int i = 0;
    int j = 1;
    int size = nums.length;
    while (j < nums.length) {
        if (nums[i] == nums[j]) {
            size--;
        }
        i++;
        j++;
    }
}

/*
in a loop grab an element if nums == 5;
five++, if nums == 10; if five > 0; five--; ten++;
if nums==20; if five >= 3 and ten > 0

*/

public boolean lemonadeChange(int[] bills) {
    int five = 0;
    int ten = 0;
    int twenty = 0;
    for (int i : bills) {
        if i == 5
            five++;
        else if i == 10
            if five > 0
                five--;
                ten++;
            else
                return false
        else if i == 20
            if five > 1 && ten > 1
                five--;
                ten--;
                twenty++;
            else if five > 3
                five = five - 3;
                twenty++;
            else
                return false;
    return true;
    }
}

public int maxProfit(int prices) {
   int i = 0, buy, sell, profit = 0, N = prices.length-1;
   while (i < N){
       while (i < N && prices[i+1] <= prices[i]) i++;
       buy = prices[i];
       while (i < N && prices[i+1] > prices[i]) i++;
       sell = prices[i];
       
       profit += sell - buy;
   }
   return profit;
}

/*
Sliding Window: intialize out = 0;
totalSum = 0; start -= 1;
in a loop add each element to totalSum
then in a while loop check if totalSum > target
totalSum = totalSum - arr[start]
start += 1;
out = out + i - start
*/

public int productSubarrays(arr, target) {
    int out = 0;
    int totalProd = 1;
    int start = -1;
    for (int i : arr) {
        totalProd = totalProd * i;
        while (totalProd > target) {
            start++;
            totalProd = totalProd / arr[start];
        }
        out = out + i - start;
    }
    return out;
}


/* 3 sum */

public int threeSum(int[] arr, target){
    arr = Array.sort(arr);
    ArrayList<Int> card = new ArrayList<Int>();
    int i = 0;
    int j = 1;
    int k = arr.length-1;
    for (int i = 0; i < arr.length-2; i++) {
        while(j < k) {
            if (arr[i]+arr[j]+arr[k]) === target {
                card.add([arr[i],arr[j],arr[k]])
                j++;
                k--;
            }
            if (arr[i]+arr[j]+arr[k]) > target
                k--;
            else
                j++;
        }
    }
    
}