K-Balanced Linked List

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given a singly linked list and an integer K. A node in the list is considered "k-balanced" if the absolute difference between the sum of values of all nodes before it and the sum of values of all nodes after it is less than or equal to K.

| (Sum of values before the node) - (Sum of values after the node) | <= K

The sum of nodes before the head of the list is 0. The sum of nodes after the tail of the list is also 0.

Your task is to determine if every node in the linked list is k-balanced. If all nodes satisfy this condition, return true. If even one node fails the check, return false. An empty list or a list with a single node is considered balanced by definition.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains the node data for the linked list, separated by single spaces. The input is terminated by -1.

The second line contains a single integer K.

Output Format:

Print true if all nodes in the list are k-balanced, and false otherwise.

Note:

The sums can become very large, so be sure to use a 64-bit integer type (like long in Java or long long in C++).

Sample Input 1:

3 2 10 7 8 -1
30

Sample Output 1:

true

Explanation for Sample 1:

Node 3: leftSum=0, rightSum=27. |0-27|=27 <= 30. OK.
Node 2: leftSum=3, rightSum=25. |3-25|=22 <= 30. OK.
Node 10: leftSum=5, rightSum=15. |5-15|=10 <= 30. OK.
Node 7: leftSum=15, rightSum=8. |15-8|=7 <= 30. OK.
Node 8: leftSum=22, rightSum=0. |22-0|=22 <= 30. OK.
All nodes are balanced.

Sample Input 2:

10 2 8 2 10 -1
2

Sample Output 2:

false

Explanation for Sample 2:

Node 10 (head): leftSum=0, rightSum=22. |0-22|=22. Since 22 > 2, this node is not balanced. We can stop and return false immediately.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

0 <= Number of nodes <= 10^5
0 <= K <= 10^14
-10^9 <= Node Value <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

K-Balanced Linked List

Console