Minimum length Sublist of K sum in singly Linked List
Given a singly linked list and an integer K. The task is to find the minimum sublist in the linked list such that the sum of the elements in that sublist is equal to K. The minimum sublist is defined as the one with the smallest number of nodes.
Examples:
Input: Linked List: 4 -> 6 -> 1 -> 2 -> 5 -> 3 -> NULL, K = 3
Output: 3 -> NULL
Explanation:
- The sublist 3 adds up to K, and its length is 1.
- There is another sublist 1 -> 2 whose sum is also K, but its length is 2, so it is not the minimum sublist.
Input: Linked List: 4 -> 11 -> 8 -> 2 -> 5 -> 2 -> 5 -> 4 -> NULL, K = 9
Output: 5 -> 4 -> NULL
Explanation:
- The sublist 5 -> 4 adds up to K, and its length is 2.
- There is another sublist 2 -> 5 -> 2 whose sum is also K, but its length is 3, so it is not the minimum sublist.
Approach: Follow the below idea to solve the given problem:
The idea behind this approach is iterating through the given linked list to find the minimum sublist with a sum equal to the target value ‘K’.
- It maintains two pointers: ‘current’ for the potential starting point of the sublist and ‘minStart‘ to track the minimum sublist found.
- As the code traverses the list, it calculates the sum and length of sublists.
- If a sublist’s sum matches ‘K‘, it compares its length to the minimum length found so far (‘minLen’).
- If the current sublist is shorter, it updates `minLen` and `minStart` to store the minimum sublist.
- This process continues for all possible starting points, ensuring that the final result is the minimum sublist meeting the sum requirement.
Steps of the above approach:
- Initialize a pointer current to the head of the linked list and minStart to NULL. Also, initialize minLen to a very large value (in this case, INT_MAX) to keep track of the minimum sublist length.
- Iterate through the linked list using the current pointer, which represents the potential start of the sublist.
- For each potential start, traverse the linked list from that point using another pointer temp. While traversing, maintain a sum and a len variable. sum keeps track of the sum of elements in the current sublist, and len keeps track of the length of the current sublist.
- Check if sum equals K. If it does, compare the current len with the minLen. If the current len is smaller, update minLen and minStart accordingly.
- Continue this process for all potential starting points in the linked list.
- Finally, return the sublist pointed to by minStart as the minimum sublist with a sum equal to K.
Below is the implementation provided:
C++
#include <bits/stdc++.h> using namespace std; // Define a struct for a singly // linked list node struct ListNode { int val; ListNode* next; ListNode( int x) : val(x) , next(NULL) { } }; // Function to find the minimum // sublist with a sum of k ListNode* findMinimumSublist(ListNode* head, int k) { // Pointer to traverse the linked list ListNode* current = head; // Pointer to the start of // the minimum sublist ListNode* minStart = NULL; // Initialize minimum length with // a large value int minLen = INT_MAX; while (current) { // Initialize sum for the current sublist int sum = 0; // Initialize length of the current sublist int len = 0; // Create a temporary pointer for // traversing the sublist ListNode* temp = current; // Traverse the sublist starting // from 'current' while (temp) { // Add the value to the // current sum sum += temp->val; // Increment the length len++; // If the sum matches 'k', check // if it's the minimum length if (sum == k) { if (len < minLen) { minLen = len; minStart = current; } } // Move to the next node in // the sublist temp = temp->next; } // Move to the next // potential starting point current = current->next; } // Return the minimum sublist // (or NULL if not found) return (minStart) ? minStart : NULL; } // Function to print the elements // of a linked list void printList(ListNode* head) { while (head) { cout << head->val << " -> "; head = head->next; } cout << "NULL" << endl; } // Drivers code int main() { // Create two linked lists ListNode* head1 = new ListNode(4); head1->next = new ListNode(6); head1->next->next = new ListNode(1); head1->next->next->next = new ListNode(2); head1->next->next->next->next = new ListNode(5); head1->next->next->next->next->next = new ListNode(3); ListNode* head2 = new ListNode(4); head2->next = new ListNode(11); head2->next->next = new ListNode(8); head2->next->next->next = new ListNode(2); head2->next->next->next->next = new ListNode(5); head2->next->next->next->next->next = new ListNode(2); head2->next->next->next->next->next->next = new ListNode(5); head2->next->next->next->next->next->next->next = new ListNode(4); int k1 = 3; int k2 = 9; // Find and print the minimum sublists // for each linked list ListNode* result1 = findMinimumSublist(head1, k1); ListNode* result2 = findMinimumSublist(head2, k2); cout << "Output 1: "; printList(result1); cout << "Output 2: "; printList(result2); return 0; } |
Java
// Define a class for a singly linked list node class ListNode { int val; ListNode next; public ListNode( int x) { val = x; next = null ; } } // Class to find the minimum sublist with a sum of k public class MinimumSublistSum { public static ListNode findMinimumSublist(ListNode head, int k) { // Pointer to traverse the linked list ListNode current = head; // Pointer to the start of the minimum sublist ListNode minStart = null ; // Initialize minimum length with a large value int minLen = Integer.MAX_VALUE; while (current != null ) { // Initialize sum for the current sublist int sum_val = 0 ; // Initialize length of the current sublist int len = 0 ; // Create a temporary pointer for traversing the sublist ListNode temp = current; // Traverse the sublist starting from 'current' while (temp != null ) { // Add the value to the current sum sum_val += temp.val; // Increment the length len++; // If the sum matches 'k', check if it's the minimum length if (sum_val == k) { if (len < minLen) { minLen = len; minStart = current; } } // Move to the next node in the sublist temp = temp.next; } // Move to the next potential starting point current = current.next; } // Return the minimum sublist (or null if not found) return minStart; } // Function to print the elements of a linked list public static void printList(ListNode head) { while (head != null ) { System.out.print(head.val + " -> " ); head = head.next; } System.out.println( "NULL" ); } // Driver code public static void main(String[] args) { // Create two linked lists ListNode head1 = new ListNode( 4 ); head1.next = new ListNode( 6 ); head1.next.next = new ListNode( 1 ); head1.next.next.next = new ListNode( 2 ); head1.next.next.next.next = new ListNode( 5 ); head1.next.next.next.next.next = new ListNode( 3 ); ListNode head2 = new ListNode( 4 ); head2.next = new ListNode( 11 ); head2.next.next = new ListNode( 8 ); head2.next.next.next = new ListNode( 2 ); head2.next.next.next.next = new ListNode( 5 ); head2.next.next.next.next.next = new ListNode( 2 ); head2.next.next.next.next.next.next = new ListNode( 5 ); head2.next.next.next.next.next.next.next = new ListNode( 4 ); int k1 = 3 ; int k2 = 9 ; // Find and print the minimum sublists for each linked list ListNode result1 = findMinimumSublist(head1, k1); ListNode result2 = findMinimumSublist(head2, k2); System.out.print( "Output 1: " ); printList(result1); System.out.print( "Output 2: " ); printList(result2); } } |
Python3
# Define a class for a singly # linked list node class ListNode: def __init__( self , x): self .val = x self . next = None # Function to find the minimum # sublist with a sum of k def findMinimumSublist(head, k): # Pointer to traverse the linked list current = head # Pointer to the start of # the minimum sublist minStart = None # Initialize minimum length with # a large value minLen = float ( 'inf' ) while current: # Initialize sum for the current sublist sum_val = 0 # Initialize length of the current sublist len = 0 # Create a temporary pointer for # traversing the sublist temp = current # Traverse the sublist starting # from 'current' while temp: # Add the value to the current sum sum_val + = temp.val # Increment the length len + = 1 # If the sum matches 'k', check # if it's the minimum length if sum_val = = k: if len < minLen: minLen = len minStart = current # Move to the next node in # the sublist temp = temp. next # Move to the next # potential starting point current = current. next # Return the minimum sublist # (or None if not found) return minStart # Function to print the elements # of a linked list def printList(head): while head: print (head.val, "->" , end = " " ) head = head. next print ( "NULL" ) # Driver code if __name__ = = "__main__" : # Create two linked lists head1 = ListNode( 4 ) head1. next = ListNode( 6 ) head1. next . next = ListNode( 1 ) head1. next . next . next = ListNode( 2 ) head1. next . next . next . next = ListNode( 5 ) head1. next . next . next . next . next = ListNode( 3 ) head2 = ListNode( 4 ) head2. next = ListNode( 11 ) head2. next . next = ListNode( 8 ) head2. next . next . next = ListNode( 2 ) head2. next . next . next . next = ListNode( 5 ) head2. next . next . next . next . next = ListNode( 2 ) head2. next . next . next . next . next . next = ListNode( 5 ) head2. next . next . next . next . next . next . next = ListNode( 4 ) k1 = 3 k2 = 9 # Find and print the minimum sublists # for each linked list result1 = findMinimumSublist(head1, k1) result2 = findMinimumSublist(head2, k2) print ( "Output 1:" , end = " " ) printList(result1) print ( "Output 2:" , end = " " ) printList(result2) |
C#
using System; // Define a class for a singly // linked list node public class ListNode { public int val; public ListNode next; public ListNode( int x) { val = x; next = null ; } } public class MainClass { // Function to find the minimum // sublist with a sum of k public static ListNode FindMinimumSublist(ListNode head, int k) { // Pointer to traverse the linked list ListNode current = head; // Pointer to the start of // the minimum sublist ListNode minStart = null ; // Initialize minimum length with // a large value int minLen = int .MaxValue; while (current != null ) { // Initialize sum for the current sublist int sum = 0; // Initialize length of the current sublist int len = 0; // Create a temporary pointer for // traversing the sublist ListNode temp = current; // Traverse the sublist starting // from 'current' while (temp != null ) { // Add the value to the // current sum sum += temp.val; // Increment the length len++; // If the sum matches 'k', check // if it's the minimum length if (sum == k) { if (len < minLen) { minLen = len; minStart = current; } } // Move to the next node in // the sublist temp = temp.next; } // Move to the next // potential starting point current = current.next; } // Return the minimum sublist // (or null if not found) return minStart; } // Function to print the elements // of a linked list public static void PrintList(ListNode head) { while (head != null ) { Console.Write(head.val + " -> " ); head = head.next; } Console.WriteLine( "NULL" ); } // Driver code public static void Main() { // Create two linked lists ListNode head1 = new ListNode(4); head1.next = new ListNode(6); head1.next.next = new ListNode(1); head1.next.next.next = new ListNode(2); head1.next.next.next.next = new ListNode(5); head1.next.next.next.next.next = new ListNode(3); ListNode head2 = new ListNode(4); head2.next = new ListNode(11); head2.next.next = new ListNode(8); head2.next.next.next = new ListNode(2); head2.next.next.next.next = new ListNode(5); head2.next.next.next.next.next = new ListNode(2); head2.next.next.next.next.next.next = new ListNode(5); head2.next.next.next.next.next.next.next = new ListNode(4); int k1 = 3; int k2 = 9; // Find and print the minimum sublists // for each linked list ListNode result1 = FindMinimumSublist(head1, k1); ListNode result2 = FindMinimumSublist(head2, k2); Console.Write( "Output 1: " ); PrintList(result1); Console.Write( "Output 2: " ); PrintList(result2); } } |
Javascript
class ListNode { constructor(x) { this .val = x; this .next = null ; } } // Function to find the minimum sublist with sum of k function GFG(head, k) { // Pointer to traverse the linked list let current = head; // Pointer to the start of the minimum sublist let minStart = null ; // Initialize minimum length with a large value let minLen = Number.POSITIVE_INFINITY; while (current) { // Initialize sum for the current sublist let sum_val = 0; let len = 0; // Create a temporary pointer for the traversing the sublist let temp = current; // Traverse the sublist starting from 'current' while (temp) { // Add the value to the current sum sum_val += temp.val; // Increment the length len++; // If the sum matches 'k' // check if it's the minimum length if (sum_val === k) { if (len < minLen) { minLen = len; minStart = current; } } // Move to the next node in the sublist temp = temp.next; } // Move to the next potential starting point current = current.next; } // Return the minimum sublist return minStart; } // Function to print the elements of the linked list function printList(head) { let result = ' '; while (head) { result += head.val + ' -> '; head = head.next; } result += ' NULL'; console.log(result); } // Driver code // Create two linked lists const head1 = new ListNode(4); head1.next = new ListNode(6); head1.next.next = new ListNode(1); head1.next.next.next = new ListNode(2); head1.next.next.next.next = new ListNode(5); head1.next.next.next.next.next = new ListNode(3); const head2 = new ListNode(4); head2.next = new ListNode(11); head2.next.next = new ListNode(8); head2.next.next.next = new ListNode(2); head2.next.next.next.next = new ListNode(5); head2.next.next.next.next.next = new ListNode(2); head2.next.next.next.next.next.next = new ListNode(5); head2.next.next.next.next.next.next.next = new ListNode(4); const k1 = 3; const k2 = 9; // Find and print the minimum sublists for the each linked list const result1 = GFG(head1, k1); const result2 = GFG(head2, k2); console.log( "Output 1:" , end= " " ); printList(result1); console.log( "Output 2:" , end= " " ); printList(result2); |
Output 1: 3 -> NULL Output 2: 5 -> 4 -> NULL
Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(1), We are not using any extra space.