Kadane's Algorithm and Linked-list intersection
Filed under Amazon
Free read 3 of 3Maintain current_max and global_max. Update current_max as max(num, current_max + num).
The question
Identify and implement Kadane's Algorithm to find the maximum subarray sum in an array, and find the intersection node of two singly linked lists.
Constraints
- Kadane's: O(N) time, O(1) space
- Intersection: O(N+M) time, O(1) space
Examples
- Input
- Kadane: [-2,1,-3,4,-1,2,1,-5,4]
- Output
- 6
- Why
- The subarray [4,-1,2,1] has the largest sum.
Approach
Maintain current_max and global_max. Update current_max as max(num, current_max + num).
Use two pointers. Traverse both lists. When a pointer hits null, redirect it to the head of the other list.
The pointers will meet at the intersection node or both will become null.
Tips
- What they are testing: Test Kadane with all negative numbers; test intersection with lists of different lengths.
- Common mistake: In intersection, failing to reset pointers after reaching the end of the first list.
Follow-ups
- Given a tree with only parent pointers, how to find the LCA?
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.