Sensor Packet Detector 15 — Problem Statement & Solution Guide

Linked ListMediumRecursive Backtracking

TimeO(n)

SpaceO(n)

Problem Description

You are given the head of a singly‑linked list where each node stores an integer value. A detector can be activated on any node, which adds that node's value to the total detector score. However, activating the detector on a node forces the next node to be skipped (the detector cannot be activated on two consecutive nodes). Determine the maximum possible detector score that can be achieved by choosing an optimal set of nodes to activate. The solution must be derived using a recursive backtracking approach (with memoization to avoid exponential blow‑up). Return the maximum score as a 64‑bit signed integer.

DSA Pattern Breakdown

"Sensor Packet Detector 15"

medium

WHY DOES IT MATTER?

This pattern is fundamental for optimization problems on linear sequences with local constraints. It appears in problems like 'Maximum Subarray', 'House Robber', and 'Best Time to Buy and Sell Stock'. Mastering it demonstrates an understanding of how to break down a global optimization problem into local sub-problems that can be solved efficiently using memoization or bottom-up DP.

OPTIMIZATION CHALLENGE

The key insight is recognizing the overlapping subproblems. A naive recursive solution recalculates the same sub-problems exponentially. By using memoization (top-down) or a DP array (bottom-up), you reduce the time complexity from O(2^n) to O(n). The space optimization challenge is reducing the O(n) DP array to O(1) by realizing that only the last two states are needed to compute the current state.

REAL-WORLD CONNECTION

This is analogous to resource allocation in distributed systems where you have a sequence of tasks or servers. If you allocate a heavy load to one server, the next server must be kept idle for cooling or maintenance. The goal is to maximize total throughput (score) while respecting the cooling constraint (skip next). It also resembles scheduling jobs on a single machine where certain jobs have cooldown periods.

In an interview, start by defining the state clearly: 'Let dp[i] be the maximum score achievable starting from node i.' Then, explicitly state the recurrence relation. If the list is singly linked, mention that you might need to convert it to an array first for easier indexing, or use recursion with memoization. Always ask about edge cases: empty list, single node, all negative values.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

This problem is a classic application of Dynamic Programming (DP) on a linear structure, specifically the 'House Robber' pattern. The core constraint—that selecting a node forces the skipping of the next node—creates a dependency between adjacent decisions. At any given node, you have two mutually exclusive choices: either you activate the detector on the current node (adding its value to the score and forcing a jump to the node after the next), or you skip the current node (adding zero to the score and moving to the next node). The optimal solution for the current state is the maximum of these two paths. This recursive structure naturally leads to a recurrence relation: dp[i] = max(dp[i+1], dp[i+2] + val[i]).

Interview Questions on This Problem

Q1How would you modify this solution if the linked list were circular, meaning the last node is connected to the first?

For a circular list, you cannot select both the first and last nodes. The standard approach is to run the linear DP algorithm twice: once excluding the first node (from index 1 to n-1) and once excluding the last node (from index 0 to n-2). The final answer is the maximum of these two results. This ensures the circular constraint is respected without complex state tracking.

Q2Can you solve this in-place without using an auxiliary array for DP, and what is the space complexity then?

Yes, since each state dp[i] only depends on dp[i+1] and dp[i+2], you can use two variables to keep track of the maximum score for the next and next-next nodes. By traversing the list from tail to head (or using a recursive memoization approach), you can reduce the space complexity from O(n) to O(1) if you are allowed to modify the list or use a stack for recursion, though O(1) iterative space is tricky on a singly-linked list without reversal. Typically, O(n) space is accepted for the DP array, but O(1) extra space is possible if you reverse the list or use a specific iterative technique with two pointers if the list were doubly linked.

Q3What if the values in the nodes could be negative? How does that change the strategy?

If values can be negative, the logic remains the same: max(skip, take). However, you must ensure that your base cases handle negative values correctly. You should not assume that skipping is always better if the current value is negative; you must still compare dp[i+1] vs dp[i+2] + val[i]. If all values are negative, the optimal score might be 0 (if you can choose to activate no detectors) or the least negative value (if you must activate at least one). Clarify the constraints: if 'maximum score' allows for zero activations, initialize the base case appropriately to allow for a score of 0.

Examples

Example 1

Input

[4,2,7,3,6]

Output

Explanation: Consider the list 4→2→7→3→6. The optimal activation pattern is: activate node 4 (score 4), skip node 2, activate node 7 (score 7), skip node 3, activate node 6 (score 6). Total = 4+7+6 = 17, which is the highest achievable sum.

Example 2

Input

[5,1,1,5]

Output

Explanation: List: 5→1→1→5. Activating the first node (5) forces skipping the second. Then we can activate the fourth node (5). The third node is skipped because its predecessor (second) was not activated, but activating it would prevent the fourth node, yielding a lower total. Best sum = 5+5 = 10.

Example 3

Input

[2,1,4,9,3]

Output

Explanation: List: 2→1→4→9→3. One optimal choice is to activate nodes with values 2, 4, and 9. After activating 2 we skip 1, activate 4, skip 9's predecessor (which is 4) is allowed, then activate 9 and skip 3. Sum = 2+4+9 = 15, which cannot be improved by any other combination.

Constraints

1 <= number of nodes <= 100000
-10^9 <= node.val <= 10^9
The algorithm must run in O(n) time and O(n) auxiliary space (for memoization).
Recursion depth will not exceed the number of nodes; tail‑call optimization is not required.

Optimal Approach & Strategy

Use dynamic programming with memoization or a bottom-up DP array to store the maximum score for each node, ensuring each sub-problem is solved only once. This reduces the time complexity to O(n) and space complexity to O(n), which can be further optimized to O(1) space by only keeping track of the last two computed values.

Brute Force Approach

Use recursion to explore all possible combinations of activating and skipping detectors, calculating the total score for each path. This results in an exponential time complexity of O(2^n) because it recalculates the same sub-problems multiple times.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @return {number}
 */
var detectScore = function(head) {
    if (!head) return 0;
    
    let take = 0;
    let skip = 0;
    
    while (head) {
        const currentTake = head.val + skip;
        const currentSkip = take;
        
        take = currentTake;
        skip = currentSkip;
        
        head = head.next;
    }
    
    return Math.max(take, skip);
};

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    int detectScore(ListNode* head) {
        if (!head) return 0;
        
        int take = 0, skip = 0;
        
        while (head) {
            int currentTake = head->val + skip;
            int currentSkip = take;
            
            take = currentTake;
            skip = currentSkip;
            
            head = head->next;
        }
        
        return max(take, skip);
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int detectScore(ListNode head) {
        if (head == null) return 0;
        
        int take = 0;
        int skip = 0;
        
        while (head != null) {
            int currentTake = head.val + skip;
            int currentSkip = take;
            
            take = currentTake;
            skip = currentSkip;
            
            head = head.next;
        }
        
        return Math.max(take, skip);
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def detectScore(self, head: Optional[ListNode]) -> int:
        if not head:
            return 0
        
        take = 0
        skip = 0
        
        while head:
            current_take = head.val + skip
            current_skip = take
            
            take = current_take
            skip = current_skip
            
            head = head.next
        
        return max(take, skip)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @return {number}
 */
var detectScore = function(head) {
    if (!head) return 0;
    
    let take = 0;
    let skip = 0;
    
    while (head) {
        const currentTake = head.val + skip;
        const currentSkip = take;
        
        take = currentTake;
        skip = currentSkip;
        
        head = head.next;
    }
    
    return Math.max(take, skip);
};

Asked in Top Tech Interviews

GoogleAmazonMicrosoft

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Sensor Packet Detector 15 Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Linked List

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Sensor Packet Detector 15 — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor