Longest Subarray with Target Sum (C Program)
C
Hard
3 views
Problem Description
Find the longest subarray whose sum is equal to a - Mechanism to find matching sums by prefix sum and hashmap it?
Official Solution
#include <stdio.h>
#include <stdlib.h>
// Simple hash map node
struct Node {
int key;
int value;
struct Node* next;
};
// Hash function
int hash(int key, int size) {
return (key % size + size) % size; // handle negative keys
}
// Insert key-value if key not present
void insert(struct Node** table, int size, int key, int value) {
int h = hash(key, size);
struct Node* node = table[h];
while (node) {
if (node->key == key)
return; // already exists
node = node->next;
}
// insert at head
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->key = key;
newNode->value = value;
newNode->next = table[h];
table[h] = newNode;
}
// Search key
int search(struct Node** table, int size, int key) {
int h = hash(key, size);
struct Node* node = table[h];
while (node) {
if (node->key == key)
return node->value;
node = node->next;
}
return -1; // not found
}
int main() {
int arr[100], n, target;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter array elements:n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter target sum: ");
scanf("%d", &target);
int size = 2*n; // hash table size
struct Node* table[size];
for (int i = 0; i < size; i++) table[i] = NULL;
int currentSum = 0;
int maxLength = 0;
for (int i = 0; i < n; i++) {
currentSum += arr[i];
if (currentSum == target) {
if (i + 1 > maxLength)
maxLength = i + 1;
}
int prevIndex = search(table, size, currentSum - target);
if (prevIndex != -1) {
if (i - prevIndex > maxLength)
maxLength = i - prevIndex;
}
if (search(table, size, currentSum) == -1) {
insert(table, size, currentSum, i);
}
}
printf("Length of longest subarray with sum %d = %dn", target, maxLength);
return 0;
}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!