package com.fishercoder.solutions;

import java.util.Arrays;

/**
 * 1099. Two Sum Less Than K
 *
 * Given an array A of integers and integer K,
 * return the maximum S such that there exists i < j with A[i] + A[j] = S and S < K.
 * If no i, j exist satisfying this equation, return -1.
 *
 * Example 1:
 * Input: A = [34,23,1,24,75,33,54,8], K = 60
 * Output: 58
 * Explanation:
 * We can use 34 and 24 to sum 58 which is less than 60.
 *
 * Example 2:
 * Input: A = [10,20,30], K = 15
 * Output: -1
 * Explanation:
 * In this case it's not possible to get a pair sum less that 15.
 *
 * Note:
 * 1 <= A.length <= 100
 * 1 <= A[i] <= 1000
 * 1 <= K <= 2000
 * */
public class _1099 {
    public static class Solution1 {
        /**
         * Time: O(n^2)
         * Space: O(1)
         * */
        public int twoSumLessThanK(int[] A, int K) {
            int maxSum = Integer.MIN_VALUE;
            for (int i = 0; i < A.length - 1; i++) {
                for (int j = i + 1; j < A.length; j++) {
                    if (A[i] + A[j] < K) {
                        maxSum = Math.max(maxSum, A[i] + A[j]);
                    }
                }
            }
            return maxSum == Integer.MIN_VALUE ? -1 : maxSum;
        }
    }

    public static class Solution2 {
        /**
         * Time: O(nlogn)
         * Space: O(1)
         * */
        public int twoSumLessThanK(int[] A, int K) {
            Arrays.sort(A);
            int left = 0;
            int right = A.length - 1;
            int sum = Integer.MIN_VALUE;
            while (left < right) {
                int newSum = A[left] + A[right];
                if (newSum < K && newSum > sum) {
                    sum = newSum;
                } else if (newSum >= K) {
                    right--;
                } else {
                    left++;
                }
            }
            return sum == Integer.MIN_VALUE ? -1 : sum;
        }
    }
}

@@ -59,610 +59,8 @@
 s;%0A%0A
-/**%0A * 1099. Two Sum Less Than K%0A *%0A * Given an array A of integers and integer K,%0A * return the maximum S such that there exists i %3C j with A%5Bi%5D + A%5Bj%5D = S and S %3C K.%0A * If no i, j exist satisfying this equation, return -1.%0A *%0A * Example 1:%0A * Input: A = %5B34,23,1,24,75,33,54,8%5D, K = 60%0A * Output: 58%0A * Explanation:%0A * We can use 34 and 24 to sum 58 which is less than 60.%0A *%0A * Example 2:%0A * Input: A = %5B10,20,30%5D, K = 15%0A * Output: -1%0A * Explanation:%0A * In this case it's not possible to get a pair sum less that 15.%0A *%0A * Note:%0A * 1 %3C= A.length %3C= 100%0A * 1 %3C= A%5Bi%5D %3C= 1000%0A * 1 %3C= K %3C= 2000%0A * */%0A
 publ
@@ -171,34 +171,32 @@
 e: O(1)%0A        
- *
  */%0A        publ
@@ -727,24 +727,24 @@
 e: O(1)%0A
+
         
  * */%0A  
@@ -735,18 +735,16 @@
         
- *
  */%0A    

refactor 1099