Maximum Value at a Given Index in a Bounded Array LeetCode solution in Java

1
/* Intuition:
2
As the number of elements is 10^9 so we can't actually create the array
3
And by seeing the limit we can judge that the complexity should be O(logn)
4
So it will become obvious that binary search can only help to solve this prob
5

6
We have to put the maximum possible value in the index position and then all
7
the values to its right and left should decrease by 1 until the value reaches 1
8
for Ex in n = 6, index = 1,  maxSum = 10
9

10
our index at 1 should be 3 and the array will look like
11
2  3  2 1 1
12
+ max - - same
13

14
means you have to make an array which is strictly increasing and it attains its max (which is answer)
15
then strictly decreasing till value becomes 1 and then continues it as 1. Like
16
1 ... 1, 2, 3, 4, 5, 6(if answer is 6), 5, 4, 3, 2, 1, .... 1
17

18
Why this solution?
19
Because our objective is to maximize our index position value i.e. ans. So to maximize it
20
we all the other elements other than index position should be as low as possible (so that sum of our array
21
is less than maxSum), which will lead to this solution of "Get the max element on index given and decrease strictly
22
on both sides of the array till our value is 1, and then continue it to 1"
23
*/
24

25
class Solution {
26
  public int maxValue(int n, int index, int maxSum) {
27
    // Setting the initial values is very important, our ans can never be 0 so set low as 1
28
    int low = 1, mid = 0, high = 1000000000;
29
    while (low <= high) {
30
      mid = (low + high) / 2;
31

32
      // If our ans (which is mid) is making the sum of array more than maxSum means we have to
33
      // decrease our high
34
      if (calcAns(mid, index, n) > maxSum) {
35
        high = mid - 1;
36
      }
37

38
      // If our ans (which is mid) is so low that even ans + 1 (i.e. mid + 1) is giving better
39
      // result that means increase our low
40
      else if (calcAns(mid + 1, index, n) <= maxSum) {
41
        low = mid + 1;
42
      }
43

44
      // If our ans (== mid) is such that the sum of array is less than maxSum and even increasing 1
45
      // to mid will result the total
46
      // sum to increase from maxSum, that signifies that we have the answer as mid
47
      else {
48
        break;
49
      }
50
    }
51

52
    return mid;
53
  }
54

55
  public int calcAns(int max, int idx, int n) {
56

57
    // This method will give you answer of the setup where our peak element is ans at index idx and
58
    // we have n elements
59
    // So we have two part of array one is the left part (1, 1... 2, 3 ... max - 1) and then (max,
60
    // max - 1, max - 2, 1 ... 1)
61
    // so you can think of it as we have few extraOnes on both left and right parts and then an AP
62
    // array which goes upto max
63

64
    // Left part I have taken till max - 1 and right part I have taken from max.
65
    // calcPart takes (first value of AP, number of elements)
66

67
    long ret = calcPart(max - 1, idx) + calcPart(max, n - idx);
68
    if (ret > 1000000000) {
69
      // Seeing the constraints, if you chose to take high mid value then it might overflow from
70
      // int. And our answer can never
71
      // be greater than 10^9 so limit it to that.
72
      return 1000000001;
73
    } else {
74

75
      // This is the sum of the array where max is taken as answer
76
      return (int) ret;
77
    }
78
  }
79

80
  public long calcPart(int a, int num) {
81

82
    // For AP we need first element (which is "a") and last element (which we calculate in an)
83
    long an = 0, extraOnes = 0;
84
    long ans = 0;
85
    if (num >= a) {
86

87
      // If total number of elements is more than a which means it will look like
88
      // a, a - 1, a - 2,  ... , 2, 1 ... followed by extraOnes
89
      an = 1;
90
      extraOnes = num - a;
91
    } else if (num < a) {
92

93
      // If total number of elements is such that we never reach 1 as our last element means
94
      // a, a - 1, a - 2 ... a - x, then extraOnes will be 0
95
      extraOnes = 0;
96
      an = a - num + 1;
97
    }
98

99
    // Sum of AP where we know first and last element = ((first + last) * n) / 2
100
    ans = ((an + a) * (a - an + 1)) / 2;
101

102
    // Add extra ones
103
    ans += extraOnes;
104

105
    return ans;
106
  }
107
}