Reference: LeetCode
Difficulty: Easy

My Post: [Java] Brute-Force and Sorting + Two Pointers (comments)

Problem

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
2
3
4
5
6
7
8
9
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.

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

Analysis

Brute-Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int twoSumLessThanK(int[] A, int K) {
  // Assume A[i] >= 1, K >= 1
  int n = A.length;
  int maxSum = -1;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      int sum = A[i] + A[j];
      if (sum < K && sum > maxSum) {
        maxSum = sum;
      }
    }
  }
  return maxSum;
}

Time: $O(N^2)$
Space: $O(1)$

Sorting & Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int twoSumLessThanK(int[] A, int K) {
  // Assume A[i] >= 1, K >= 1
  // Sorting
  Arrays.sort(A);
  // Two Pointers
  int maxSum = -1;
  int n = A.length;
  int lo = 0, hi = n - 1;
  while (lo < hi) {
    int sum = A[lo] + A[hi];
    if (sum >= K) {
      --hi;
    } else { // sum < K
      if (sum > maxSum) maxSum = sum; // update
      ++lo;
    }
  }
  return maxSum;
}

Time: $O(N\log{N})$
Space: $O(1)$

Amazon OA | Movies on Flight

Problem: Amazon | OA 2019 | Movies on Flight

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public static void main(String[] args) {
  List<Integer> movieDurations = new ArrayList<>();
  movieDurations.add(90);
  movieDurations.add(85);
  movieDurations.add(75);
  movieDurations.add(60);
  movieDurations.add(120);
  movieDurations.add(150);
  movieDurations.add(125); // [0, 6]
  int d = 250;
  System.out.println(Arrays.toString(pairOfLongestMovies(movieDurations, d)));
}

static class Movie {
  int id;
  int duration;
  Movie(int i, int d) {
    id = i;
    duration = d;
  }
}

public static int[] pairOfLongestMovies(List<Integer> movieDurations, int d) {
  // Assume movieDurations is not null, size >= 2
  int n = movieDurations.size();
  List<Movie> movies = new ArrayList<>();
  for (int i = 0; i < n; ++i) {
    movies.add(new Movie(i, movieDurations.get(i)));
  }
  // Sort
  Collections.sort(movies, (m1, m2) -> {
    return m1.duration - m2.duration;
  });
  // Two Pointers
  int lo = 0, hi = n - 1;
  int maxLen = -1;
  int maxLo = -1, maxHi = -1;
  while (lo < hi) {
    int sum = movies.get(lo).duration + movies.get(hi).duration;
    if (sum > d - 30) {
      --hi;
    } else { // sum <= d - 30
      if (sum > maxLen) { // update
        maxLen = sum;
        maxLo = lo;
        maxHi = hi;
      }
      if (sum == d - 30) break;
      ++lo;
    }
  }
  return new int[] { movies.get(maxLo).id, movies.get(maxHi).id };
}