Facebook Pixel

3287. Find the Maximum Sequence Value of Array

HardBit ManipulationArrayDynamic Programming
Leetcode Link

Problem Description

You are given an integer array nums and a positive integer k.

The value of a sequence seq of size 2 * x is defined as:

  • (seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1]).

Return the maximum value of any subsequence of nums having size 2 * k.

Intuition

To solve this problem, we can use a dynamic programming approach combined with prefix and suffix decomposition. Our aim is to find two subsequences of length k from nums that maximize the XOR of the ORs of the elements in these subsequences.

Here's the detailed thought process:

  1. Dynamic Programming Definition: We define two 3D DP arrays:

    • f[i][j][x] indicates whether a subset of size j from the first i elements of nums can achieve an OR value of x.
    • g[i][j][y] indicates whether a subset of size j from the elements starting at index i of nums can achieve an OR value of y.

  2. State Transition:

    • For f: We can either include the current element or not in our subset. If included, the OR value would be updated. 
      f[i + 1][j][x] = f[i][j][x]  // not include nums[i]
f[i + 1][j + 1][x | nums[i]] = f[i][j][x]  // include nums[i]
    • For g: Similar to f, but in reverse from the end of the array. 
      g[i - 1][j][y] = g[i][j][y]  // not include nums[i-1]
g[i - 1][j + 1][y | nums[i - 1]] = g[i][j][y]  // include nums[i-1]

  3. Combining Results:

    • Once f and g are fully populated, we iterate over potential partition points where we divide nums into two parts: the first k elements for f and the last k elements for g.
    • We calculate XOR for every combination of valid OR values from f and g and keep track of the maximum value.

  4. Result: The maximum XOR found across all possible partitions gives the desired result.

This systematic approach ensures that we consider all possible subsequence configurations efficiently.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution utilizes a dynamic programming strategy along with prefix and suffix decomposition to achieve the desired result. Here's how the solution is implemented:

Dynamic Programming Arrays

  1. Arrays f and g:

    • f[i][j][x]: Represents whether a subset of size j selected from the first i elements of nums can achieve an OR value of x.
    • g[i][j][y]: Represents whether a subset of size j starting at index i can achieve an OR value of y.

  2. Initialization:

    • Initialize f[0][0][0] = True because an empty subset has an OR value of 0.
    • Similarly, initialize g[n][0][0] = True for suffix starts.

State Transitions

  1. Filling f array:

    • Iterate over each element i in nums.
    • For each possible subset size j, and each possible OR value x, update f with these transitions: 
      f[i + 1][j][x] = f[i][j][x]  // We don't include nums[i] in the subset
f[i + 1][j + 1][x | nums[i]] = f[i][j][x]  // We include nums[i] in the subset

  2. Filling g array:

    • Start iteration from the last element backward.
    • Apply similar logic as f to populate g: 
      g[i - 1][j][y] = g[i][j][y]  // We don't include nums[i-1] in the subset
g[i - 1][j + 1][y | nums[i - 1]] = g[i][j][y]  // We include nums[i-1] in the subset

Combining Results

  1. Maximizing XOR:

    • For possible partition points i between k and n-k, evaluate every combination of OR values x from f and y from g.
    • If both f[i][k][x] and g[i][k][y] are True, calculate x ^ y and update ans if it is greater than the current ans.

  2. Return the Maximum Value:

    • The result will be stored in ans, which contains the maximum XOR value over all valid partitions.

This approach efficiently considers all potential subsequences by leveraging the power of dynamic programming to store intermediate OR results for fast XOR calculations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walkthrough the solution approach using the following example:

Assume you have the array nums = [1, 2, 3, 4] and k = 1.

  1. Dynamic Programming Arrays (f and g):

    We need to evaluate subsequences of length 2 * k = 2 and find the maximum value of the expression defined. Let's define our 3D DP arrays f and g.

  2. Initialization:

    • For f: Initialize f[0][0][0] = True because an empty subset can always have an OR value of 0.

    • For g: Initialize g[n][0][0] = True where n = 4.

  3. Filling f array:

    Let's iterate through nums to fill f.

    • For i = 0:

      • f[1][0][0] = f[0][0][0]
      • f[1][1][1] = f[0][0][0] because 1 | 0 = 1

    • For i = 1:

      • f[2][0][0] = f[1][0][0]
      • f[2][1][2] = f[1][0][0] because 2 | 0 = 2
      • f[2][1][3] = f[1][1][1] because 2 | 1 = 3

    • Similar logic applies for i = 2 and i = 3.

  4. Filling g array:

    Iterate backward for g, starting from the end of nums.

    • For i = 3:

      • g[2][0][0] = g[3][0][0]
      • g[2][1][4] = g[3][0][0] because 4 | 0 = 4

    • For i = 2:

      • g[1][0][0] = g[2][0][0]
      • g[1][1][3] = g[2][0][0] because 3 | 0 = 3
      • g[1][1][7] = g[2][1][4] because 3 | 4 = 7

    • Follow the similar logic for other indices.

  5. Maximizing XOR:

    Now, consider potential partition points where the first k elements are selected from the left (f) and the last k elements from the right (g).

    • For partition after index 1 (k = 1 and n-k = 3):
      • Compare potential values: e.g., from f[1][1][1] and combinations from g[1][1][...].
      • Calculate XOR values 1 ^ 4 = 5, etc.

  6. Result:

    The maximum XOR value found during this process will be the result. Based on this approach and given numbers, the maximum value would be stored and returned as the answer.

This example illustrates how dynamic programming helps efficiently calculate and store intermediate results, leading to determining the maximal XOR value for the given subsequences configuration.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxValue(self, nums: List[int], k: int) -> int:
5        # Define the maximum bit mask range
6        max_mask = 1 << 7
7        n = len(nums)
8
9        # Dynamic programming table for forward direction
10        fwd_dp = [[[False] * max_mask for _ in range(k + 2)] for _ in range(n + 1)]
11        fwd_dp[0][0][0] = True
12
13        # Fill the forward DP table
14        for i in range(n):
15            for j in range(k + 1):
16                for x in range(max_mask):
17                    # Maintain the current state
18                    fwd_dp[i + 1][j][x] |= fwd_dp[i][j][x]
19                    # Update state for including current number
20                    fwd_dp[i + 1][j + 1][x | nums[i]] |= fwd_dp[i][j][x]
21
22        # Dynamic programming table for backward direction
23        bwd_dp = [[[False] * max_mask for _ in range(k + 2)] for _ in range(n + 1)]
24        bwd_dp[n][0][0] = True
25
26        # Fill the backward DP table
27        for i in range(n, 0, -1):
28            for j in range(k + 1):
29                for y in range(max_mask):
30                    # Maintain the current state
31                    bwd_dp[i - 1][j][y] |= bwd_dp[i][j][y]
32                    # Update state for including current number
33                    bwd_dp[i - 1][j + 1][y | nums[i - 1]] |= bwd_dp[i][j][y]
34
35        # Initialize the answer variable
36        ans = 0
37
38        # Calculate the maximum value of x ^ y
39        for i in range(k, n - k + 1):
40            for x in range(max_mask):
41                if fwd_dp[i][k][x]:   # Check valid split in forward direction
42                    for y in range(max_mask):
43                        if bwd_dp[i][k][y]:  # Check valid split in backward direction
44                            # Update the maximum value
45                            ans = max(ans, x ^ y)
46
47        return ans
48
1class Solution {
2
3    // This method finds the maximum value obtained by choosing two non-overlapping 
4    // subarrays of size 'k' from the `nums` array, where the value is obtained by 
5    // the XOR of OR results of both subarrays.
6    public int maxValue(int[] nums, int k) {
7        int maxBitValue = 1 << 7; // Set this to cover numbers up to 2^7 - 1.
8        int arrayLength = nums.length;
9      
10        // Initialize the boolean DP table for forward processing
11        boolean[][][] forwardDP = new boolean[arrayLength + 1][k + 2][maxBitValue];
12        forwardDP[0][0][0] = true;
13
14        // Fill out forwardDP table based on choosing or not choosing the current element.
15        for (int i = 0; i < arrayLength; i++) {
16            for (int j = 0; j <= k; j++) {
17                for (int x = 0; x < maxBitValue; x++) {
18                    if (forwardDP[i][j][x]) {
19                        // Don't pick the current element
20                        forwardDP[i + 1][j][x] = true;
21                        // Pick the current element
22                        forwardDP[i + 1][j + 1][x | nums[i]] = true;
23                    }
24                }
25            }
26        }
27
28        // Initialize the boolean DP table for backward processing
29        boolean[][][] backwardDP = new boolean[arrayLength + 1][k + 2][maxBitValue];
30        backwardDP[arrayLength][0][0] = true;
31
32        // Fill out backwardDP table based on choosing or not choosing the current element.
33        for (int i = arrayLength; i > 0; i--) {
34            for (int j = 0; j <= k; j++) {
35                for (int y = 0; y < maxBitValue; y++) {
36                    if (backwardDP[i][j][y]) {
37                        // Don't pick the current element
38                        backwardDP[i - 1][j][y] = true;
39                        // Pick the current element
40                        backwardDP[i - 1][j + 1][y | nums[i - 1]] = true;
41                    }
42                }
43            }
44        }
45
46        int maxResult = 0;
47
48        // Search for the maximum XOR value in the overlapping valid state space
49        for (int i = k; i <= arrayLength - k; i++) {
50            for (int x = 0; x < maxBitValue; x++) {
51                if (forwardDP[i][k][x]) {
52                    for (int y = 0; y < maxBitValue; y++) {
53                        if (backwardDP[i][k][y]) {
54                            maxResult = Math.max(maxResult, x ^ y);
55                        }
56                    }
57                }
58            }
59        }
60
61        return maxResult;
62    }
63}
64
1class Solution {
2public:
3    int maxValue(vector<int>& nums, int k) {
4        int mask = 1 << 7; // The mask for 7 bits, representing the maximum possible XOR value
5        int n = nums.size(); // Size of the input array nums
6
7        // Create a 3-dimensional vector to bool, initialized to 'false'.
8        // f[i][j][x] means we can reach the state where we chose j numbers with an XOR sum of x using the first i numbers.
9        vector<vector<vector<bool>>> f(n + 1, vector<vector<bool>>(k + 2, vector<bool>(mask, false)));
10      
11        f[0][0][0] = true; // Base case: With 0 elements picked, we have 0 as the sum of XOR.
12
13        // Fill up the dp table 'f' to represent subsets of the array from the start
14        for (int i = 0; i < n; ++i) {
15            for (int j = 0; j <= k; ++j) {
16                for (int x = 0; x < mask; ++x) {
17                    if (f[i][j][x]) {
18                        f[i + 1][j][x] = true; // Without choosing nums[i]
19                        f[i + 1][j + 1][x | nums[i]] = true; // Choosing nums[i]
20                    }
21                }
22            }
23        }
24
25        // Create another 3-dimensional vector to track subsets from the end
26        vector<vector<vector<bool>>> g(n + 1, vector<vector<bool>>(k + 2, vector<bool>(mask, false)));
27      
28        g[n][0][0] = true; // Base case for the reverse direction
29
30        // Fill up the dp table 'g' to represent subsets of the array from the end
31        for (int i = n; i > 0; --i) {
32            for (int j = 0; j <= k; ++j) {
33                for (int y = 0; y < mask; ++y) {
34                    if (g[i][j][y]) {
35                        g[i - 1][j][y] = true; // Without choosing nums[i-1]
36                        g[i - 1][j + 1][y | nums[i - 1]] = true; // Choosing nums[i-1]
37                    }
38                }
39            }
40        }
41
42        int ans = 0; // Initialize the maximum XOR value
43
44        // Iterate over all possible positions to split the array
45        for (int i = k; i <= n - k; ++i) {
46            for (int x = 0; x < mask; ++x) {
47                if (f[i][k][x]) {
48                    for (int y = 0; y < mask; ++y) {
49                        if (g[i][k][y]) {
50                            ans = max(ans, x ^ y); // Calculate the maximum XOR value
51                        }
52                    }
53                }
54            }
55        }
56
57        return ans; // Return the maximum XOR value achieved
58    }
59};
60
1function maxValue(nums: number[], k: number): number {
2    // Set the maximum possible bitwise value for 7 bits
3    const m = 1 << 7;
4    const n = nums.length;
5
6    // Initialize a 3D array for forward dynamic programming
7    const f: boolean[][][] = Array.from({ length: n + 1 }, () =>
8        Array.from({ length: k + 2 }, () => Array(m).fill(false))
9    );
10    f[0][0][0] = true; // Base case: Start with no elements selected and zero value
11
12    // Populate the forward DP table
13    for (let i = 0; i < n; i++) {
14        for (let j = 0; j <= k; j++) {
15            for (let x = 0; x < m; x++) {
16                if (f[i][j][x]) {
17                    f[i + 1][j][x] = true; // Do not include nums[i]
18                    f[i + 1][j + 1][x | nums[i]] = true; // Include nums[i]
19                }
20            }
21        }
22    }
23
24    // Initialize a 3D array for reverse dynamic programming
25    const g: boolean[][][] = Array.from({ length: n + 1 }, () =>
26        Array.from({ length: k + 2 }, () => Array(m).fill(false))
27    );
28    g[n][0][0] = true; // Base case: Start with no elements selected and zero value
29
30    // Populate the reverse DP table
31    for (let i = n; i > 0; i--) {
32        for (let j = 0; j <= k; j++) {
33            for (let y = 0; y < m; y++) {
34                if (g[i][j][y]) {
35                    g[i - 1][j][y] = true; // Do not include nums[i-1]
36                    g[i - 1][j + 1][y | nums[i - 1]] = true; // Include nums[i-1]
37                }
38            }
39        }
40    }
41
42    let ans = 0; // Variable to store the maximum XOR value
43
44    // Evaluate all possible splits and calculate maximum XOR
45    for (let i = k; i <= n - k; i++) {
46        for (let x = 0; x < m; x++) {
47            if (f[i][k][x]) {
48                for (let y = 0; y < m; y++) {
49                    if (g[i][k][y]) {
50                        ans = Math.max(ans, x ^ y);
51                    }
52                }
53            }
54        }
55    }
56
57    return ans;
58}
59

Time and Space Complexity

The given code computes maximum values using dynamic programming by maintaining two 3D arrays f and g with dimensions (n + 1) x (k + 2) x m. Here, n is the length of the nums list, and m is 2^7.

  • Each of the arrays f and g requires a three-level nested loop to fill values, running (n) x (k + 1) x m iterations in the maxValue function. Therefore, the operations involving both f and g contribute to the overall time complexity.

  • Calculating the ans variable involves a nested loop across all possible values for x and y, resulting in (k) x ((n - k + 1) x m x m) operations in the second segment of the code where ans is computed.

In conclusion, the time complexity is O(n \times m \times k), and the space complexity is also O(n \times m \times k). This aligns with the reference answer specification.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

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

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

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

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More