1184. Distance Between Bus Stops

A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given start and destination stops.

1
2
3

Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

class Solution {
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
        int sum1 = 0;
        int sum2 = 0;
        if(start > destination){
            int tmp = start;
            start = destination;
            destination = tmp;
        }
        for(int i=start; i<destination; i++)
        {
             sum1 += distance[i];
        }    
        for(int i=destination; i<start+distance.size(); i++)
            sum2 += distance[i%distance.size()];
        if(sum1 < sum2) return sum1;
        else return sum2;
    }
};

1185. Day of the Week

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the day, month and year respectively.

Return the answer as one of the following values {“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”, “Saturday”}.

Example 1:

Input: day = 31, month = 8, year = 2019
Output: "Saturday"
Example 2:

Input: day = 18, month = 7, year = 1999
Output: "Sunday"
Example 3:

Input: day = 15, month = 8, year = 1993
Output: "Sunday"

class Solution {
public:
        string dayOfTheWeek(int day, int month, int year) {
            string daysInWeek[7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
            int DaysByMonthMod7[12] = {0,3,2,5,0,3,5,1,4,6,2,4};
            if(month < 3) year -= 1;
            return daysInWeek[(year + (year/4 -year/100 + year/400) + DaysByMonthMod7[month-1] + day) % 7];
        }      
};

Constraints:

The given dates are valid dates between the years 1971 and 2100.

1186. Maximum Subarray Sum with One Deletion

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Example 1:

Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.
Example 2:

Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.
Example 3:

Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4

class Solution {
public:
    int maximumSum(vector<int>& v) {
        int res = 0, n = v.size();
        int cur_max = v[0], overall_max = v[0];
        vector<int> f(n);
        vector<int> b(n);
        f[0] = v[0];
        
        for(int i=1; i<n; i++)
        {
            cur_max = max(v[i], cur_max+v[i]);
            overall_max = max(overall_max, cur_max);
            
            f[i] = cur_max;
        }
        
        cur_max = overall_max = b[n-1] = v[n-1];
        for(int i=n-2; i>=0; i-- )
        {
            cur_max = max(v[i], cur_max + v[i]);
            overall_max = max(overall_max, cur_max);
            
            b[i] = cur_max;
        }
        
        res = overall_max;
        for(int i=1; i<n-1; i++)
        {
            res = max(res, f[i-1] + b[i+1]);
        }
        
        return res;
    }
};

1187. Make Array Strictly Increasing

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].
Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].
Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

class Solution {
public:
    int dp[2001][2001] = {};

    int dfs(vector<int>& a1, vector<int>&a2, int i1, int i2, int prev){
        if(i1 >= a1.size()) return 0;
        i2 = upper_bound(begin(a2) + i2, end(a2), prev) - begin(a2);
        if(dp[i1][i2]) return dp[i1][i2];
        int r1 = i2 < a2.size() ? 1 + dfs(a1, a2, i1+1, i2+1, a2[i2]) : a2.size()+1;
        int r2 = prev < a1[i1] ? dfs(a1, a2, i1+1, i2, a1[i1]) : a2.size()+1;
        dp[i1][i2] = min(r1, r2);
        return dp[i1][i2];
    }
    
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(), arr2.end());
        int res = dfs(arr1, arr2, 0, 0, INT_MIN);
        return res > arr2.size() ? -1 : res;
    }
};