LeetCode 1793. Maximum Score of a Good Subarray (Hard) : NileshBlog.Tech

LeetCode 1793. Maximum Score of a Good Subarray :Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Maximum Score of a Good Subarray” or “LeetCode 1793. ‘

Table of Contents

Appraoch : Two Pointer

Input Parameters: The code takes two inputs – an array ‘A’ or (nums in Leetcode given) and an integer ‘k’ as the index.
Initialization: Initialize two pointers ‘i’ and ‘j’ to ‘k-1’ and ‘k+1’ respectively. ‘N’ is the length of array ‘A’. ‘res’ is initialized to ‘A[k]’ (the value at index ‘k’), and ‘mn’ is also set to ‘A[k]’ initially.

Algorithm: The code uses a while loop that iterates as long as ‘i’ is greater than or equal to 0 or ‘j’ is less than ‘N’. This loop is the core of the algorithm.
Pointer Movement: Inside the loop, the code checks whether ‘i’ is less than 0 or if ‘A[j]’ is greater than ‘A[i’. Depending on the condition, ‘mn’ is updated with the minimum of ‘mn’ and ‘A[j]’ or ‘A[i]’, and the corresponding pointer (‘i’ or ‘j’) is incremented or decremented accordingly.
Result Update: The code then calculates the score by multiplying ‘mn’ with the difference between ‘j’ and ‘i’ and updates ‘res’ with the maximum of the current ‘res’ and this score.

Output: The final ‘res’ value holds the maximum score, which is the answer to the problem.

dry run of the given code with the example ‘A = [1,4,3,7,4,5]’ and ‘k = 3’:

i=k-1 && j=k+1 starting with:

Iteration	i	j	A[i]	A[j]	mn	j – i – 1	res
0	2	4	3	4	7	1	7
1	2	5	3	5	7	2	8
2	1	5	4	5	4	3	15
3	0	5	1	5	1	4	15
4	0	6	1	4	1	5	15

DRY and RUN of Exampe of two pointer approach

First max we found out result at (1,5) index. SO our result ==15

Codes : Two Pointer Approach

C++: LeetCode 1793. Maximum Score of a Good Subarray

class Solution {
public:
    int maximumScore(vector<int>& A, int k) {
        int i = k - 1, j = k + 1, N = A.size(), res = A[k], mn = A[k];
        while (i >= 0 || j < N) {
            if (i < 0 || (j < N && A[j] > A[i])) {
                mn = min(mn, A[j]);
                ++j;
            } else {
                mn = min(mn, A[i]);
                --i;
            }
            res = max(res, mn * (j - i - 1));
        }
        return res;
    }
};

Java: LeetCode 1793. Two Pointer Approach

class Solution {
    public int maximumScore(int[] A, int k) {
        int i = k - 1, j = k + 1, N = A.length, res = A[k], mn = A[k];
        while (i >= 0 || j < N) {
            if (i < 0 || (j < N && A[j] > A[i])) {
                mn = Math.min(mn, A[j]);
                ++j;
            } else {
                mn = Math.min(mn, A[i]);
                --i;
            }
            res = Math.max(res, mn * (j - i - 1));
        }
        return res;
    }
}

Python: Maximum Score of a Good Subarray Two Pointer Approach

class Solution:
    def maximumScore(self, A, k):
        i = k - 1
        j = k + 1
        N = len(A)
        res = A[k]
        mn = A[k]
        while i >= 0 or j < N:
            if i < 0 or (j < N and A[j] > A[i]):
                mn = min(mn, A[j])
                j += 1
            else:
                mn = min(mn, A[i])
                i -= 1
            res = max(res, mn * (j - i - 1))
        return res

JavaScript: LeetCode 1793

class Solution {
    maximumScore(A, k) {
        let i = k - 1;
        let j = k + 1;
        const N = A.length;
        let res = A[k];
        let mn = A[k];
        while (i >= 0 || j < N) {
            if (i < 0 || (j < N && A[j] > A[i])) {
                mn = Math.min(mn, A[j]);
                j++;
            } else {
                mn = Math.min(mn, A[i]);
                i--;
            }
            res = Math.max(res, mn * (j - i - 1));
        }
        return res;
    }
}

Dart: Maximum Score of a Good Subarray

class Solution {
int maximumScore(List<int> A, int k) {
  int i = k - 1, j = k + 1, N = A.length, res = A[k], mn = A[k];
  while (i >= 0 || j < N) {
    if (i < 0 || (j < N && A[j] > A[i])) {
      mn = (mn < A[j]) ? mn : A[j];
      j++;
    } else {
      mn = (mn < A[i]) ? mn : A[i];
      i--;
    }
    res = (res > mn * (j - i - 1)) ? res : mn * (j - i - 1);
  }
  return res;
}

}

Swift: LeetCode 1793. Maximum Score of a Good Subarray

class Solution {
   func maximumScore(_ A: [Int], _ k: Int) -> Int {
    var i = k - 1, j = k + 1, N = A.count, res = A[k], mn = A[k]
    while i >= 0 || j < N {
        if i < 0 || (j < N && A[j] > A[i]) {
            mn = min(mn, A[j])
            j += 1
        } else {
            mn = min(mn, A[i])
            i -= 1
        }
        res = max(res, mn * (j - i - 1))
    }
    return res
}
}

Kotlin: LeetCode Maximum Score of a Good Subarray

class Solution {
fun maximumScore(A: IntArray, k: Int): Int {
    var i = k - 1
    var j = k + 1
    val N = A.size
    var res = A[k]
    var mn = A[k]
    while (i >= 0 || j < N) {
        if (i < 0 || (j < N && A[j] > A[i])) {
            mn = minOf(mn, A[j])
            j++
        } else {
            mn = minOf(mn, A[i])
            i--
        }
        res = maxOf(res, mn * (j - i - 1))
    }
    return res
}
}

Rust: LeetCode 1793. Maximum Score of a Good Subarray

fn maximum_score(a: Vec<i32>, k: usize) -> i32 {
    let mut i = k as i32 - 1;
    let mut j = k + 1;
    let n = a.len();
    let mut res = a[k];
    let mut mn = a[k];
    while i >= 0 || j < n {
        if i < 0 || (j < n && a[j] > a[i as usize]) {
            mn = std::cmp::min(mn, a[j]);
            j += 1;
        } else {
            mn = std::cmp::min(mn, a[i as usize]);
            i -= 1;
        }
        res = std::cmp::max(res, mn * (j as i32 - i - 1));
    }
    res
}

Go: LeetCode 1793. Maximum Score of a Good Subarray

package main

import "fmt"

func maximumScore(A []int, k int) int {
    i := k - 1
    j := k + 1
    N := len(A)
    res := A[k]
    mn := A[k]
    for i >= 0 || j < N {
        if i < 0 || (j < N && A[j] > A[i]) {
            if mn > A[j] {
                mn = A[j]
            }
            j++
        } else {
            if mn > A[i] {
                mn = A[i]
            }
            i--
        }
        if res < mn*(j-i-1) {
            res = mn * (j - i - 1)
        }
    }
    return res
}

LeetCode 1793. Maximum Score of a Good Subarray (Hard)