2786. Visit Array Positions to Maximize Score

MediumArrayDynamic Programming
Leetcode Link

Problem Description

You are provided with an int array nums that is 0-indexed and a positive int x. The goal is to calculate the maximum total score you can obtain starting at position 0 of the array and moving to any subsequent position. The rules are outlined as follows:

  • You can move from your current position i to any position j such that i < j.
  • When you visit position i, you earn nums[i] points added to your score.
  • If you move between positions i and j and nums[i] and nums[j] have different parities (one is odd, the other is even), you lose x points from your score.

You kick off with nums[0] points, and you have to figure out the maximum score that can be achieved under these conditions.

Intuition

The task is to maximize the score while taking into account that moving between numbers of different parity comes with a penalty of x points. To do this, we need to use dynamic programming to track the highest scores while considering the parity of the current number.

Here's an outline of the approach:

  • Initialize a list f with two elements, set to negative infinity [-inf, -inf]. This list will keep track of the max scores for even and odd indices.
  • Set the element of f corresponding to the parity of nums[0] (even or odd) to nums[0]. This represents the score starting at position 0.
  • Iterate through the nums array starting from index 1. For each value v at index i:
    • Calculate the maximum score when staying on the same parity (f[v & 1] + v) and when changing parity (f[v & 1 ^ 1] + v - x).
    • Update f[v & 1] with the highest score from the above step.
  • After processing all elements, the maximum score will be the maximum element from f.

The key intuition in this solution comes from recognizing that at any index i in the array, you have two scenarios to consider:

  1. The last score came from an index with the same parity as i. In this case, you just add the current value to the previous score since no penalty is incurred.
  2. The last score came from an index with different parity. Here, you add the current value to the previous score from the opposite parity and subtract the penalty x.

This process will lead us to the highest possible score, taking into account the penalty for switching parities.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The implementation uses a dynamic programming approach to compute the maximum score. Here's a step-by-step walkthrough:

  • Firstly, the algorithm initializes a list f with two elements, [-inf, -inf]. This record is to keep track of the two possible states for our score related to parity: even (0) and odd (1). In Python, -inf denotes negative infinity which is a useful placeholder for "not yet computed or improbably low score."

  • The first element of nums is factored into our initial state. Since we always start at position 0, f[nums[0] & 1] is set to nums[0]. The expression nums[0] & 1 will be 0 if nums[0] is even, and 1 if it is odd, so it determines the index of f that gets updated.

  • The algorithm then iterates through elements in nums starting from index 1. For each value v, it computes the two possible scenarios:

    • Staying on the same parity (f[v & 1] + v),
    • Switching parity (f[v & 1 ^ 1] + v - x). The ^ operator is a bitwise XOR, which flips the bit, effectively getting us the other parity.

    The update for the score at parity v & 1 chooses whichever of these two possibilities gives a higher score. This is done by the max function.

  • After evaluating all elements in nums, the maximum score is the highest value in f, which can be obtained using Python's built-in max(f) function.

The code snippet provided succinctly translates this approach into a Python function as part of a Solution class:

1class Solution:
2    def maxScore(self, nums: List[int], x: int) -> int:
3        f = [-inf] * 2
4        f[nums[0] & 1] = nums[0]
5        for v in nums[1:]:
6            f[v & 1] = max(f[v & 1] + v, f[v & 1 ^ 1] + v - x)
7        return max(f)

Each iteration effectively represents a choice at every position i with a value v from nums: taking its score as part of the existing parity sequence or starting a new sequence of the opposite parity with an x penalty. The algorithm dynamically keeps track of the best choice by updating only the score of the relevant parity after each decision. This pattern avoids the need for recursive traversal through all potential positions and parities, significantly reducing the complexity of the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have the array nums = [4, 5, 2, 7, 3] and the penalty x = 3.

We initiate the variable f with two elements [-inf, -inf] to keep track of the max scores for the even (f[0]) and odd indices (f[1]).

  • f = [-inf, -inf]

Starting at position 0, nums[0] = 4, which is even, so we update f[0] with the value of nums[0].

  • f = [4, -inf]

We move to nums[1] = 5, which is odd:

  • If we stay with odd, f[1] would become 5 (since -inf + 5 is just 5), but there's a catch: we start from an even index so we must apply the penalty x. The new score would be 5 - 3 = 2.
  • If we switch to even, f[0] + nums[1] would be 4 + 5 = 9. We take the max of both, which is 9, so we update f[1].
  • f = [4, 9]

Next, nums[2] = 2, which is even:

  • Staying with even parity, f[0] + 2 = 4 + 2 = 6.
  • Switching to odd, f[1] + 2 - x = 9 + 2 - 3 = 8. The higher score is 8, so f[0] becomes 8.
  • f = [8, 9]

With nums[3] = 7, which is odd:

  • Staying odd, f[1] + 7 = 9 + 7 = 16.
  • Switching to even, f[0] + 7 - x = 8 + 7 - 3 = 12. We take the max which is 16 and update f[1].
  • f = [8, 16]

Lastly, nums[4] = 3, which is odd:

  • Staying odd, f[1] + 3 = 16 + 3 = 19.
  • Switching to even, f[0] + 3 - x = 8 + 3 - 3 = 8. The max is 19, so f[1] remains 19.
  • f = [8, 19]

The maximum score we can get is max(f), which is 19.

The entire process demonstrates the dynamic programming algorithm's effectiveness in computing the maximum score by considering the penalty for switching between even and odd numbers. Each decision is based on whether to continue the sequence of the current parity or start a new one of the opposite parity with a penalty. The algorithm avoids the need to check each path separately, instead of using a running tally that gets updated in each step, which is considerably more efficient.

Solution Implementation

1from typing import List
2import math
3
4class Solution:
5    def maxScore(self, nums: List[int], x: int) -> int:
6        # Initialize a list with two elements representing negative infinity
7        # The list is used to track the maximum scores for even and odd numbers separately
8        max_scores = [-math.inf, -math.inf]
9      
10        # The first number's score is determined based on its parity (even/odd)
11        # and assigned as the initial score for that parity 
12        max_scores[nums[0] % 2] = nums[0]
13      
14        # Iterate over the remaining numbers starting from the second element
15        for value in nums[1:]:
16            # Determine the parity of the current number, 0 if even, 1 if odd
17            parity = value % 2
18            # Update the score for the current parity
19            # max() is choosing the greater value between continuing the same parity
20            # or switching parity and applying the penalty/subtraction of x
21            max_scores[parity] = max(max_scores[parity] + value, max_scores[parity ^ 1] + value - x)
22      
23        # Return the maximum score between the even and odd parities
24        return max(max_scores)
25
1class Solution {
2
3    // Method to calculate the maximum score.
4    public long maxScore(int[] nums, int x) {
5      
6        // Array f to store the current maximum score for odd and even indexed numbers.
7        long[] maxScoreForOddEven = new long[2];
8      
9        // Initialize both entries with a very small number to simulate negative infinity.
10        Arrays.fill(maxScoreForOddEven, -(1L << 60));
11      
12        // The first number decides the initial maximum score for its parity (odd or even).
13        maxScoreForOddEven[nums[0] & 1] = nums[0];
14
15        // Iterate over the array, starting from the second element.
16        for (int i = 1; i < nums.length; ++i) {
17          
18            // numParity is 0 for even and 1 for odd.
19            int numParity = nums[i] & 1;
20          
21            // Update the maximum score for the current parity (odd or even).
22            maxScoreForOddEven[numParity] = Math.max(
23                maxScoreForOddEven[numParity] + nums[i],              // Case when adding the current number to the same parity.
24                maxScoreForOddEven[numParity ^ 1] + nums[i] - x       // Case when adding the current number leads to change in parity
25                                                                    // with the penalty x.
26            );
27        }
28      
29        // Return the maximum score among the two parities.
30        return Math.max(maxScoreForOddEven[0], maxScoreForOddEven[1]);
31    }
32}
33
1#include <vector>
2#include <algorithm> // For max() function
3using namespace std;
4
5class Solution {
6public:
7    long long maxScore(vector<int>& nums, int x) {
8        // Define an infinite value for long long type
9        const long long INF = 1LL << 60;
10      
11        // Create a vector to track the maximum scores for even and odd indices
12        vector<long long> maxScores(2, -INF); // Initialized with -INF
13      
14        // Initialize the first element of the score according to whether it's even or odd
15        maxScores[nums[0] & 1] = nums[0];
16
17        // Calculate the number of elements
18        int n = nums.size();
19
20        // Loop over the elements starting from the second element
21        for (int i = 1; i < n; ++i) {
22            // Update the max score for the current parity (even/odd index) of the number
23            // This is the maximum of either adding the current number to the existing
24            // score of the same parity, or switching parity and subtracting the penalty x
25            maxScores[nums[i] & 1] = max(
26                maxScores[nums[i] & 1] + nums[i],             // Same parity: add current number
27                maxScores[(nums[i] & 1) ^ 1] + nums[i] - x   // Opposite parity: switch parity and subtract x
28            );
29        }
30
31        // Return the maximum value of the two max scores
32        return max(maxScores[0], maxScores[1]);
33    }
34};
35
1function maxScore(nums: number[], x: number): number {
2    // Define a very large number to represent "infinity".
3    const INFINITY = 1 << 30;
4    // Initialize an array 'scores' with two elements representing the max scores for even and odd indices.
5    const scores: number[] = Array(2).fill(-INFINITY);
6    // For the first number, update the score based on it being even or odd.
7    scores[nums[0] & 1] = nums[0];
8
9    // Loop through the numbers starting from the second element.
10    for (let i = 1; i < nums.length; ++i) {
11        const isOdd = nums[i] & 1;
12        // Update the score for the current parity (even or odd).
13        // The updated score is the max of the current score for the same parity plus the current number,
14        // or the score for the other parity plus the current number minus x.
15        scores[isOdd] = Math.max(scores[isOdd] + nums[i], scores[isOdd ^ 1] + nums[i] - x);
16    }
17
18    // Return the maximum score between the even and odd indices.
19    return Math.max(scores[0], scores[1]);
20}
21
Not Sure What to Study? Take the 2-min Quiz

How many times is a tree node visited in a depth first search?

Time and Space Complexity

The given Python code snippet aims to calculate a certain "maximum score" by iterating through the input list nums and applying some operations based on the elements' parity (odd or even) and a given integer x. To analyze the time and space complexity of this code, let's consider n to be the length of the input list nums.

Time Complexity

The time complexity of this code is determined by the number of operations performed in the for-loop that iterates through the nums list:

  • The for-loop runs (n - 1) times, as it starts from the second element in nums.
  • Within the loop, a constant number of operations are executed: two bitwise AND operations, four direct accesses by index to the list f, up to two max operations, and a few arithmetic operations.

Since these operations inside the loop are all of constant time complexity, the overall time complexity of the loop is O(n - 1). Simplifying this, we get:

O(n - 1) = O(n).

Thus, the time complexity of the code is O(n).

Space Complexity

As for the space complexity:

  • A new list f of fixed size 2 is created. This does not depend on the size of the input and is thus O(1).
  • Variable v is a single integer that is used to iterate through nums, which is also O(1) space.
  • There are no other data structures or recursive calls that use additional space that scales with the input size.

Therefore, the space complexity of the code is O(1).

Without a reference answer provided alongside the code, the analysis is based solely on the provided snippet.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«