Visit Array Positions to Maximize Score solution and explanation
9 more videos on this problem
Leetcode BiWeekly contest 109 - Medium - Visit Array Positions to Maximize ScorePrakhar Agrawal · 16:18 · 1K views
2786. Visit Array Positions to Maximize Score | O(1) Space complexity | Leetcode Biweekly 109codingMohan · 39:22 · 645 views
Visit Array Positions to Maximize Score | Leetcode 2786 | Recursion | BiWeekly 109Tech Courses · 10:38 · 630 views
Leetcode Biweekly contest 109 | Visit Array Positions to Maximize Score | Hindi Explanation | DPPawan Kumar Giri · 17:41 · 604 views
6931. Visit Array Positions to Maximize Score || Leetcode || BiWeekly Contest 109 || HindiAshish Kumar · 10:59 · 575 views
2786. Visit Array Positions to Maximize Score (Leetcode Medium)Programming Live with Larry · 16:23 · 428 views
【每日一题】LeetCode 2786. Visit Array Positions to Maximize ScoreHuifeng Guan · 9:44 · 380 views
Leetcode 2786 || Visit Array Positions to Maximize Score || Leetcode Weekly Medium || cppKomal Pal · 13:11 · 210 views
Maximize with Dynamic Programming - LeetCode 2786. Visit Array Positions to Maximize ScorevanAmsen · 4:55 · 112 views
[Eng] Leetcode | Biweekly Contest 109 | 2786 Visit Array Positions to Maximize ScoreCyCode · 8:43 · 63 views
The problem
You are given a 0-indexed integer array nums and a positive integer x.
You are initially at position 0 in the array and you can visit other positions according to the following rules:
- If you are currently in position
i, then you can move to any positionjsuch thati < j. - For each position
ithat you visit, you get a score ofnums[i]. - If you move from a position
ito a positionjand the parities ofnums[i]andnums[j]differ, then you lose a score ofx.
Return the maximum total score you can get.
Note that initially you have nums[0] points.
Example 1:
Input: nums = [2,3,6,1,9,2], x = 5 Output: 13 Explanation: We can visit the following positions in the array: 0 -> 2 -> 3 -> 4. The corresponding values are 2, 6, 1 and 9. Since the integers 6 and 1 have different parities, the move 2 -> 3 will make you lose a score of x = 5. The total score will be: 2 + 6 + 1 + 9 - 5 = 13.
Example 2:
Input: nums = [2,4,6,8], x = 3 Output: 20 Explanation: All the integers in the array have the same parities, so we can visit all of them without losing any score. The total score is: 2 + 4 + 6 + 8 = 20.
Constraints:
2 <= nums.length <= 1051 <= nums[i], x <= 106
Approach overview
Problem Overview: You start at index 0 and can move to any later index in the array. Each visited value adds to your score, but switching between even and odd numbers subtracts a penalty x. The goal is to choose positions that maximize the total score.
Approach 1: Greedy with Memoization (Top-Down DP) (O(n) time, O(n) space)
This approach models the problem as a recursive decision process. From each index, you decide which future position to visit next while tracking the parity of the last selected number. Memoization stores the best score achievable from a given index and parity state to avoid recomputation. The key observation is that the only information affecting future choices is the current index and whether the previous value was even or odd. This reduces the state space and makes the recursion efficient. This technique combines greedy selection with dynamic programming caching.
Approach 2: Dynamic Programming with Parity States (O(n) time, O(1) space)
The optimal solution keeps track of the best score achievable when the last chosen number is even and when it is odd. Maintain two variables: bestEven and bestOdd. While iterating through the array, compute the best possible score if the current number is selected. If the parity matches the previous state, simply add the value; if it differs, subtract the penalty x. Update the corresponding parity state with the maximum possible score. Because each element is processed once and only two states are maintained, the algorithm runs in linear time and constant space.
This solution works because the penalty only depends on parity changes, not on the exact index previously chosen. That allows the problem to collapse into two running states instead of tracking all previous indices. The pattern appears frequently in array optimization problems where transitions depend on limited state.
Recommended for interviews: The dynamic programming parity-state solution is what interviewers typically expect. It demonstrates the ability to compress DP state and recognize that only parity matters, reducing a potential O(n²) search to O(n). Mentioning the memoized recursive version first can show your reasoning process, but implementing the O(n) DP with two variables proves strong optimization skills.
Approach 1: Dynamic Programming Approach
The Dynamic Programming approach leverages an array dp where each element dp[i] signifies the maximum score obtainable by the time we reach the i-th index in nums. The logic involves iterating through each element and calculating the potential score by transitioning from previously visited elements to the current one, accounting for the parity penalty when applicable.
We initialize dp[0] with nums[0], as this is the starting point. For each subsequent index j, traverse all prior indices i and update dp[j] with either the current point at index j itself, or the maximum score possible by transitioning from dp[i] and adjusting for penalties where necessary. This results in O(n^2) time complexity, necessitating optimization.
def maxScore(nums, x):
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
for j in range(1, n):
dp[j] = nums[j]
for i in range(j):
penalty = x if nums[i] % 2 != nums[j] % 2 else 0
dp[j] = max(dp[j], dp[i] + nums[j] - penalty)
return max(dp)
nums = [2, 3, 6, 1, 9, 2]
x = 5
result = maxScore(nums, x)
print(f"Maximum score: {result}")import java.util.*;
public class MaxScore {
public static int maxScore(int[] nums, int x) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
for (int j = 1; j < n; j++) {
dp[j] = nums[j];
for (int i = 0; i < j; i++) {
int penalty = (nums[i] % 2 != nums[j] % 2) ? x : 0;
dp[j] = Math.max(dp[j], dp[i] + nums[j] - penalty);
}
}
int maxScore = Arrays.stream(dp).max().getAsInt();
return maxScore;
}
public static void main(String[] args) {
int[] nums = {2, 3, 6, 1, 9, 2};
int x = 5;
int result = maxScore(nums, x);
System.out.println("Maximum score: " + result);
}
}#include <iostream>
#include <vector>
#include <climits>
int maxScore(const std::vector<int>& nums, int x) {
int n = nums.size();
std::vector<int> dp(n, INT_MIN);
dp[0] = nums[0];
for (int j = 1; j < n; ++j) {
dp[j] = nums[j];
for (int i = 0; i < j; ++i) {
int penalty = (nums[i] % 2 != nums[j] % 2) ? x : 0;
dp[j] = std::max(dp[j], dp[i] + nums[j] - penalty);
}
}
return *std::max_element(dp.begin(), dp.end());
}
int main() {
std::vector<int> nums = {2, 3, 6, 1, 9, 2};
int x = 5;
int result = maxScore(nums, x);
std::cout << "Maximum score: " << result << std::endl;
return 0;
}function maxScore(nums, x) {
let n = nums.length;
let dp = new Array(n).fill(0);
dp[0] = nums[0];
for (let j = 1; j < n; j++) {
dp[j] = nums[j];
for (let i = 0; i < j; i++) {
let penalty = (nums[i] % 2 !== nums[j] % 2) ? x : 0;
dp[j] = Math.max(dp[j], dp[i] + nums[j] - penalty);
}
}
return Math.max(...dp);
}
const nums = [2, 3, 6, 1, 9, 2];
const x = 5;
console.log("Maximum score:", maxScore(nums, x));#include <stdio.h>
#include <stdlib.h>
int maxScore(int* nums, int numsSize, int x) {
int* dp = malloc(numsSize * sizeof(int));
dp[0] = nums[0];
for (int j = 1; j < numsSize; j++) {
dp[j] = nums[j];
for (int i = 0; i < j; i++) {
int penalty = (nums[i] % 2 != nums[j] % 2) ? x : 0;
dp[j] = dp[j] > dp[i] + nums[j] - penalty ? dp[j] : dp[i] + nums[j] - penalty;
}
}
int maxScore = 0;
for (int i = 0; i < numsSize; i++) {
if (dp[i] > maxScore) {
maxScore = dp[i];
}
}
free(dp);
return maxScore;
}
int main() {
int nums[] = {2, 3, 6, 1, 9, 2};
int x = 5;
int result = maxScore(nums, 6, x);
printf("Maximum score: %d\n", result);
return 0;
}using System;
public class MaxScore {
public static int MaxScore(int[] nums, int x) {
int n = nums.Length;
int[] dp = new int[n];
dp[0] = nums[0];
for (int j = 1; j < n; j++) {
dp[j] = nums[j];
for (int i = 0; i < j; i++) {
int penalty = (nums[i] % 2 != nums[j] % 2) ? x : 0;
dp[j] = Math.Max(dp[j], dp[i] + nums[j] - penalty);
}
}
int maxScore = 0;
for (int i = 0; i < n; i++) {
if (dp[i] > maxScore) {
maxScore = dp[i];
}
}
return maxScore;
}
public static void Main() {
int[] nums = {2, 3, 6, 1, 9, 2};
int x = 5;
Console.WriteLine("Maximum score: " + MaxScore(nums, x));
}
}The Python solution engages a dynamic programmatic method through a dp list where each index saves maximum scores realized engagingly at index-specific travel. Initialize from nums[0] to demarcate the inaugural point. For each j index, it assesses all prior accessible indices i with potential score adjusting in case of modulo disparities.
Execution for the function is O(n^2) thereby each loop spacing checks all possible positions anew with space of motion consolidating resulting activity. For storage, it's O(n) given single sequential dp indexing.
Approach 2: Greedy Approach with Memoization
The greedy approach, combined with memoization, aims to reduce computational time by strategically choosing the best potential next index to maximize score with minimum loss. The memoization stores results of previously computed indices, preventing re-evaluation, and improving efficiency over traditional DP.
This approach initializes a recursive function that checks transitions with penalties, caching results for overlap avoidance. It enables a selective path based on higher weightage preference calculated through indirect cached evaluations of consequences of choices, ensuring potential gain maximization in score vigilance.
def max_score_recursive(nums, memo, x, i):
if i >= len(nums):
return 0
if memo[i] != -1:
return memo[i]
max_score = 0
for j in range(i+1, len(nums)):
penalty = x if nums[i] % 2 != nums[j] % 2 else 0
max_score = max(max_score, nums[j] - penalty + max_score_recursive(nums, memo, x, j))
memo[i] = nums[i] + max_score
return memo[i]
def max_score(nums, x):
memo = [-1] * len(nums)
return max_score_recursive(nums, memo, x, 0)
nums = [2, 3, 6, 1, 9, 2]
x = 5
result = max_score(nums, x)
print(f"Maximum score: {result}")import java.util.*;
public class MaxScore {
public static int maxScoreRecursive(int[] nums, int[] memo, int x, int i) {
if (i >= nums.length) return 0;
if (memo[i] != -1) return memo[i];
int maxScore = 0;
for (int j = i+1; j < nums.length; ++j) {
int penalty = (nums[i] % 2 != nums[j] % 2) ? x : 0;
maxScore = Math.max(maxScore, nums[j] - penalty + maxScoreRecursive(nums, memo, x, j));
}
return memo[i] = nums[i] + maxScore;
}
public static int maxScore(int[] nums, int x) {
int[] memo = new int[nums.length];
Arrays.fill(memo, -1);
return maxScoreRecursive(nums, memo, x, 0);
}
public static void main(String[] args) {
int[] nums = {2, 3, 6, 1, 9, 2};
int x = 5;
System.out.println("Maximum score: " + maxScore(nums, x));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxScoreRecursive(const std::vector<int>& nums, std::vector<int>& memo, int x, int i) {
if (i >= nums.size()) return 0;
if (memo[i] != -1) return memo[i];
int maxScore = 0;
for (int j = i+1; j < nums.size(); ++j) {
int penalty = (nums[i] % 2 != nums[j] % 2) ? x : 0;
maxScore = std::max(maxScore, nums[j] - penalty + maxScoreRecursive(nums, memo, x, j));
}
return memo[i] = nums[i] + maxScore;
}
int maxScore(const std::vector<int>& nums, int x) {
std::vector<int> memo(nums.size(), -1);
return maxScoreRecursive(nums, memo, x, 0);
}
int main() {
std::vector<int> nums = {2, 3, 6, 1, 9, 2};
int x = 5;
int result = maxScore(nums, x);
std::cout << "Maximum score: " << result << std::endl;
return 0;
}function maxScoreRecursive(nums, memo, x, i) {
if (i >= nums.length) return 0;
if (memo[i] !== -1) return memo[i];
let maxScore = 0;
for (let j = i+1; j < nums.length; j++) {
let penalty = (nums[i] % 2 !== nums[j] % 2) ? x : 0;
maxScore = Math.max(maxScore, nums[j] - penalty + maxScoreRecursive(nums, memo, x, j));
}
return memo[i] = nums[i] + maxScore;
}
function maxScore(nums, x) {
let memo = new Array(nums.length).fill(-1);
return maxScoreRecursive(nums, memo, x, 0);
}
const nums = [2, 3, 6, 1, 9, 2];
const x = 5;
console.log("Maximum score:", maxScore(nums, x));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int maxScoreRecursive(int* nums, int* memo, int n, int x, int i) {
if (i >= n) return 0;
if (memo[i] != -1) return memo[i];
int maxScore = 0;
for (int j = i+1; j < n; ++j) {
int penalty = (nums[i] % 2 != nums[j] % 2) ? x : 0;
maxScore = maxScore > nums[j] - penalty + maxScoreRecursive(nums, memo, n, x, j) ? maxScore : nums[j] - penalty + maxScoreRecursive(nums, memo, n, x, j);
}
return memo[i] = nums[i] + maxScore;
}
int maxScore(int* nums, int numsSize, int x) {
int* memo = (int*)malloc(numsSize * sizeof(int));
memset(memo, -1, numsSize * sizeof(int));
int result = maxScoreRecursive(nums, memo, numsSize, x, 0);
free(memo);
return result;
}
int main() {
int nums[] = {2, 3, 6, 1, 9, 2};
int x = 5;
int result = maxScore(nums, 6, x);
printf("Maximum score: %d\n", result);
return 0;
}using System;
public class MaxScore {
public static int MaxScoreRecursive(int[] nums, int[] memo, int x, int i) {
if (i >= nums.Length) return 0;
if (memo[i] != -1) return memo[i];
int maxScore = 0;
for (int j = i+1; j < nums.Length; ++j) {
int penalty = (nums[i] % 2 != nums[j] % 2) ? x : 0;
maxScore = Math.Max(maxScore, nums[j] - penalty + MaxScoreRecursive(nums, memo, x, j));
}
return memo[i] = nums[i] + maxScore;
}
public static int MaxScore(int[] nums, int x) {
int[] memo = new int[nums.Length];
Array.Fill(memo, -1);
return MaxScoreRecursive(nums, null, x, 0);
}
public static void Main() {
int[] nums = { 2, 3, 6, 1, 9, 2 };
int x = 5;
Console.WriteLine("Maximum score: " + MaxScore(nums, x));
}
}This Python tactic expresses advantageously in recursive memoization prints allowing systemic navigation over each stance cases retrieval not hauntingly. Conditionally fetched elemented sectors insistently align reused results sidestepmodulations applied states across disparities viewpoint checks primed memoization.
O(n^2) hosting thespian span, cushioned iterative memorandum advances oversightatively divested symbiosis form inner strength O(n) pragmatism memory-wise.
Approach 3: Dynamic Programming
Based on the problem description, we can draw the following conclusions:
- Moving from position
ito positionj, ifnums[i]andnums[j]have different parities, thenxpoints will be lost; - Moving from position
ito positionj, ifnums[i]andnums[j]have the same parity, then no points will be lost.
Therefore, we can use an array f of length 2 to represent the maximum score when the current position's parity is 0 and 1. Initially, the values of f are -infty, and then we initialize f[nums[0] \& 1] = nums[0], indicating the score at the initial position.
Next, we start traversing the array nums from position 1. For each position i corresponding to the value v, we update the value of f[v \& 1] to be the larger value between f[v \& 1] and f[v \& 1 \oplus 1] - x plus v, i.e., f[v \& 1] = max(f[v \& 1], f[v \& 1 \oplus 1] - x) + v.
The answer is the larger value between f[0] and f[1].
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function maxScore(nums: number[], x: number): number {
const f: number[] = Array(2).fill(-Infinity);
f[nums[0] & 1] = nums[0];
for (let i = 1; i < nums.length; ++i) {
const v = nums[i];
f[v & 1] = Math.max(f[v & 1], f[(v & 1) ^ 1] - x) + v;
}
return Math.max(...f);
}func maxScore(nums []int, x int) int64 {
const inf int = 1 << 40
f := [2]int{-inf, -inf}
f[nums[0]&1] = nums[0]
for _, v := range nums[1:] {
f[v&1] = max(f[v&1], f[v&1^1]-x) + v
}
return int64(max(f[0], f[1]))
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Execution for the function is O(n^2) thereby each loop spacing checks all possible positions anew with space of motion consolidating resulting activity. For storage, it's O(n) given single sequential |
| Greedy Approach with Memoization | O(n^2) hosting thespian span, cushioned iterative memorandum advances oversightatively divested symbiosis form inner strength O(n) pragmatism memory-wise. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Memoization (Top-Down DP) | O(n) | O(n) | Useful for understanding the decision process and demonstrating recursion with memoization. |
| Dynamic Programming with Parity States | O(n) | O(1) | Best practical solution. Efficient for large arrays and typically expected in coding interviews. |
Frequently asked questions
Is Visit Array Positions to Maximize Score easy or hard?
The problem is rated Medium on LeetCode. The challenge is recognizing that only parity affects the penalty, allowing the dynamic programming state to be reduced to two variables instead of tracking every previous index.
How to solve Visit Array Positions to Maximize Score in O(n)?
Maintain two running scores: bestEven and bestOdd. When visiting a new number, compute the score by either continuing with the same parity or switching parity and subtracting x. Update the corresponding state with the maximum value. A single pass through the array yields the optimal result.
What is the best approach for Visit Array Positions to Maximize Score?
The optimal approach uses dynamic programming with two parity states. Track the best score when the last selected number is even and when it is odd. While iterating through the array, update these states and subtract the penalty x when parity changes. This achieves O(n) time and O(1) space complexity.
What data structure is used in Visit Array Positions to Maximize Score?
The solution mainly relies on array traversal combined with dynamic programming state tracking. Instead of storing a full DP table, two variables track the best score for even and odd parity states.
What is the time complexity of Visit Array Positions to Maximize Score?
The optimal dynamic programming solution runs in O(n) time because each element is processed exactly once. Only two state variables are maintained for even and odd parity scores, giving O(1) space complexity.
Visit Array Positions to Maximize Score Python or Java solution approach?
Both Python and Java implementations typically use the same DP strategy with two variables. Iterate through the array, update bestEven or bestOdd depending on the current number’s parity, and subtract x when switching parity. This keeps the solution O(n) with constant space.
Is Visit Array Positions to Maximize Score asked at Google, Amazon, or Meta?
This problem represents a common interview pattern involving dynamic programming state compression and parity-based transitions. Variations of this pattern frequently appear in interviews at companies like Amazon, Google, and Meta when testing optimization over arrays.