GeeksforGeeks: Indexes of Subarray Sum

 

Indexes of Subarray Sum

Difficulty: Medium

Given an array arr[] containing only non-negative integers, your task is to find a continuous subarray (a contiguous sequence of elements) whose sum equals a specified value target. You need to return the 1-based indices of the leftmost and rightmost elements of this subarray. You need to find the first subarray whose sum is equal to the target.

Note: If no such array is possible then, return [-1].

Examples:

Input: arr[] = [1, 2, 3, 7, 5], target = 12
Output: [2, 4]
Explanation: The sum of elements from 2nd to 4th position is 12.

Input: arr[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], target = 15
Output: [1, 5]
Explanation: The sum of elements from 1st to 5th position is 15.

Input: arr[] = [5, 3, 4], target = 2
Output: [-1]
Explanation: There is no subarray with sum 2.

Constraints:
1 <= arr.size()<= 106
0 <= arr[i] <= 103
0 <= target <= 109

To solve this problem efficiently, we can use a sliding window technique with the two-pointer approach. This is a very efficient way to find the subarray with a target sum in linear time, as it avoids checking all possible subarrays (which would be inefficient for large arrays).

Approach: Sliding Window (Two Pointers)

1. Start with two pointers: Begin with both pointers (start and end) at the start of the array. The end pointer will iterate over the array, and the start pointer will help in maintaining the subarray sum that matches the target.
2. Expand the window: As end moves forward, accumulate the sum of elements between the start and end pointers.
3. Shrink the window if necessary: If the sum exceeds the target, increment the start pointer to reduce the sum.
4. Check for match: If at any point the sum equals the target, return the 1-based indices of the start and end pointers.
5. Edge Case: If no subarray is found that matches the target, return [-1].

Code Implementation:

public class Solution {
    public int[] SubarraySum(int[] arr, int target) {
        int n = arr.Length;
        int start = 0, currentSum = 0;
        
        for (int end = 0; end < n; end++) {
            currentSum += arr[end];
            
            // Shrink the window from the left if the sum exceeds target
            while (currentSum > target && start <= end) {
                currentSum -= arr[start];
                start++;
            }
            
            // If current sum equals target, return the 1-based indices
            if (currentSum == target) {
                return new int[] { start + 1, end + 1 }; // 1-based index
            }
        }
        
        // If no subarray found
        return new int[] { -1 };
    }
}

Explanation:

1. Initialize start and currentSum: start is the left pointer of the window, and currentSum keeps track of the sum of elements between start and end.
2. Iterate through the array: The end pointer moves through each element, and we add the value to currentSum.
3. Shrink the window if necessary: If currentSum exceeds the target, we increment the start pointer and subtract the value at start from currentSum to reduce the sum.
4. Check for a match: Whenever currentSum equals the target, we return the 1-based indices (start + 1 and end + 1).
5. Return [-1] if no match is found: If the loop ends without finding a subarray whose sum equals the target, we return [-1].

Time Complexity:

• Time Complexity: $O(n)$, where n is the size of the array. Each element is processed at most twice (once when adding to currentSum and once when removing from currentSum).
• Space Complexity: $O(1)$ because we are only using a few variables (start, currentSum, etc.) and not using any extra space proportional to the input size.

Example Walkthrough:

Example 1:

• Input: arr[] = [1, 2, 3, 7, 5], target = 12
• Iteration steps:
  • start = 0, end = 0, sum = 1
  • start = 0, end = 1, sum = 3
  • start = 0, end = 2, sum = 6
  • start = 0, end = 3, sum = 13 → shrink the window (start = 1)
  • start = 1, end = 3, sum = 12 → found the subarray.
• Output: [2, 4] (1-based indices).

Example 2:

• Input: arr[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], target = 15
• Iteration steps:
  • start = 0, end = 4, sum = 15 → found the subarray.
• Output: [1, 5] (1-based indices).

Example 3:

• Input: arr[] = [5, 3, 4], target = 2
• No subarray with sum 2.
• Output: [-1].

This approach is optimal and ensures that we efficiently find the required subarray in linear time.

Geeksforgeeks: Kadane's Algorithm

 

Kadane's Algorithm

Difficulty: Medium

Given an integer array arr[]. You need to find the maximum sum of a subarray.

Examples:

Input: arr[] = [2, 3, -8, 7, -1, 2, 3]
Output: 11
Explanation: The subarray {7, -1, 2, 3} has the largest sum 11.

Input: arr[] = [-2, -4]
Output: -2
Explanation: The subarray {-2} has the largest sum -2.

Input: arr[] = [5, 4, 1, 7, 8]
Output: 25
Explanation: The subarray {5, 4, 1, 7, 8} has the largest sum 25.

Constraints:
1 ≤ arr.size() ≤ 105
-109 ≤ arr[i] ≤ 104

Kadane's Algorithm

Kadane's Algorithm is an efficient solution to the problem of finding the maximum sum of a subarray in an integer array. The algorithm operates in linear time $O(n)$ and requires constant space $O(1)$.

Approach:

1. Initialize two variables:

   • currentSum (the sum of the subarray being considered): It is initialized to the first element of the array.
   • maxSum (the maximum sum encountered so far): It is also initialized to the first element of the array.

2. Iterate through the array:

   • For each element, decide whether to add it to the existing subarray (currentSum) or start a new subarray with the current element. This decision is made by comparing:
     • currentSum + arr[i] (sum including the current element)
     • arr[i] (start a new subarray with the current element)
   • Update currentSum to the maximum of the two.
   • Update maxSum to keep track of the highest sum encountered.

3. Edge Case:

   • If the array contains only negative numbers, Kadane's algorithm will return the largest negative number, which is correct because the subarray with the maximum sum would be just the largest single element.

Code Implementation:

public class Solution {
    public int MaxSubArray(int[] arr) {
        // Initialize variables for current sum and maximum sum.
        int currentSum = arr[0];
        int maxSum = arr[0];
        
        // Iterate through the array from the second element.
        for (int i = 1; i < arr.Length; i++) {
            // Choose to either add the current element to the subarray
            // or start a new subarray from the current element.
            currentSum = Math.Max(arr[i], currentSum + arr[i]);
            
            // Update the maximum sum encountered so far.
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

Explanation:

1. currentSum = Math.Max(arr[i], currentSum + arr[i]):

   • If adding the current element to the currentSum results in a larger sum, continue with the subarray.
   • If not, start a new subarray from the current element.

2. maxSum = Math.Max(maxSum, currentSum):

   • Keep track of the largest sum encountered at each step.

Time Complexity:

• Time Complexity: $O(n)$, where n is the size of the input array. We iterate through the array once, performing constant time operations for each element.
• Space Complexity: $O(1)$, as we are only using a few extra variables for tracking sums, regardless of the input size.

Example Walkthrough:

Example 1:

• Input: arr[] = [2, 3, -8, 7, -1, 2, 3]
• Iteration steps:
  • currentSum = 2, maxSum = 2
  • currentSum = 5, maxSum = 5
  • currentSum = -3, maxSum = 5
  • currentSum = 7, maxSum = 7
  • currentSum = 6, maxSum = 7
  • currentSum = 8, maxSum = 8
  • currentSum = 11, maxSum = 11
• Output: 11

Example 2:

• Input: arr[] = [-2, -4]
• Iteration steps:
  • currentSum = -2, maxSum = -2
  • currentSum = -4, maxSum = -2
• Output: -2

Example 3:

• Input: arr[] = [5, 4, 1, 7, 8]
• Iteration steps:
  • currentSum = 5, maxSum = 5
  • currentSum = 9, maxSum = 9
  • currentSum = 10, maxSum = 10
  • currentSum = 17, maxSum = 17
  • currentSum = 25, maxSum = 25
• Output: 25

Edge Case:

Example 4:

• Input: arr[] = [-1, -2, -3, -4]
• Iteration steps:
  • currentSum = -1, maxSum = -1
  • currentSum = -2, maxSum = -1
  • currentSum = -3, maxSum = -1
  • currentSum = -4, maxSum = -1
• Output: -1 (since all elements are negative, the largest sum is just the least negative element).

Conclusion:

Kadane's Algorithm is a simple yet powerful technique for solving the maximum subarray sum problem in linear time. It is efficient and handles all edge cases, including arrays with all negative numbers.

Geeksforgeeks: Minimum Jumps

 

Minimum Jumps

Difficulty: Medium

You are given an array arr[] of non-negative numbers. Each number tells you the maximum number of steps you can jump forward from that position.

For example:

• If arr[i] = 3, you can jump 1 step, 2 steps, or 3 steps forward from position i.
• If arr[i] = 0, you cannot jump forward from that position.

Your task is to find the minimum number of jumps needed to move from the first position in the array to the last position.

Note:  Return -1 if you can't reach the end of the array.

Examples : 

Input: arr[] = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
Output: 3 
Explanation: First jump from 1st element to 2nd element with value 3. From here we jump to 5th element with value 9, and from here we will jump to the last. 

Input: arr = [1, 4, 3, 2, 6, 7]
Output: 2 
Explanation: First we jump from the 1st to 2nd element and then jump to the last element.

Input: arr = [0, 10, 20]
Output: -1
Explanation: We cannot go anywhere from the 1st element.

Constraints:
2 ≤ arr.size() ≤ 106
0 ≤ arr[i] ≤ 105

Minimum Jumps Problem

The goal is to find the minimum number of jumps to reach the last index of an array, where each element of the array represents the maximum number of steps you can jump forward from that position.

Approach:

We can solve this problem efficiently using a greedy approach. The main idea is to keep track of the farthest we can reach with the current jump, and when that is exceeded, we make another jump.

Key Steps:

1. Track Current and Maximum Reach:

   • currentEnd: The farthest index you can reach with the current jump.
   • farthest: The farthest index you can reach so far with the current jump or upcoming jumps.

2. Greedy Jumping:

   • Iterate through the array, and for each element, update the farthest index.
   • When the farthest index exceeds or equals the end of the array, return the jump count.
   • If we have reached the currentEnd (i.e., the farthest we can go with the current jump), increment the jump counter and update currentEnd to farthest.

3. Edge Case:

   • If at any point, the current element is 0 and it blocks progress (i.e., no possible jump forward), return -1.

Code Implementation:

public class Solution {
    public int Jump(int[] arr) {
        int n = arr.Length;
        if (n <= 1) return 0;  // No jump needed if already at the end
        
        int jumps = 0;
        int farthest = 0;
        int currentEnd = 0;
        
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.Max(farthest, i + arr[i]);  // Update the farthest reachable index
            
            // If we've reached the end of the current jump, we must make another jump
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                
                // If the current jump takes us to or beyond the end of the array, we return jumps
                if (currentEnd >= n - 1) return jumps;
            }
        }
        
        return -1;  // If we exit the loop without reaching the end, it's not possible to reach the end
    }
}

Explanation:

1. Initialization:

   • jumps: Tracks the number of jumps taken to reach the end.
   • farthest: Tracks the farthest index that can be reached from the current position.
   • currentEnd: Tracks the end of the current jump range.

2. Iterate through the array:

   • For each index i, calculate the farthest index that can be reached from index i (farthest = Math.Max(farthest, i + arr[i])).
   • If i reaches currentEnd, it means we have finished a jump and need to move to the next jump range. Update jumps and currentEnd.
   • If currentEnd reaches or exceeds n-1 (the last index), we return the number of jumps.

3. Edge Case Handling:

   • If arr[0] == 0, it's not possible to move anywhere, so return -1.

Time Complexity:

• Time Complexity: $O(n)$, where n is the length of the input array. We are iterating through the array once, and all operations within the loop are constant time.
• Space Complexity: $O(1)$, as we only use a few extra variables for tracking the jumps and indices.

Example Walkthrough:

Example 1:

• Input: arr[] = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
• Steps:
  1. Start at index 0, jump to index 1 (farthest = 3).
  2. From index 1, jump to index 5 (farthest = 9).
  3. From index 5, jump to index 10 (end).
• Output: 3

Example 2:

• Input: arr[] = [1, 4, 3, 2, 6, 7]
• Steps:
  1. Start at index 0, jump to index 1 (farthest = 5).
  2. From index 1, jump to index 5 (end).
• Output: 2

Example 3:

• Input: arr[] = [0, 10, 20]
• Steps:
  • At index 0, the element is 0, so we cannot jump anywhere.
• Output: -1

Conclusion:

The greedy approach is optimal for this problem. By keeping track of the farthest index we can reach with each jump and incrementing jumps when necessary, we can solve this problem in linear time $O(n)$.

Geeksforgeeks: Majority Element

 Majority Element

Difficulty: Medium

Given an array arr. Find the majority element in the array. If no majority exists, return -1.

A majority element in an array is an element that appears strictly more than arr.size()/2 times in the array.

Examples:

Input: arr[] = [3, 1, 3, 3, 2]
Output: 3
Explanation: Since, 3 is present more than n/2 times, so it is the majority element.

Input: arr[] = [7]
Output: 7
Explanation: Since, 7 is single element and present more than n/2 times, so it is the majority element.

Input: arr[] = [2, 13]
Output: -1
Explanation: Since, no element is present more than n/2 times, so there is no majority element.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ arr.size() ≤ 105
0 ≤ arr[i]≤ 105

Problem Overview:

The task is to find the majority element in an array. A majority element is defined as an element that appears more than n / 2 times in the array, where n is the size of the array. If no such element exists, return -1.

Approach:

To solve this problem efficiently with a time complexity of $O(n)$ and space complexity of $O(1)$, we can utilize the Boyer-Moore Voting Algorithm. This algorithm is well-suited for problems involving majority elements in arrays and works by maintaining a candidate element and a counter.

Key Idea:

• Boyer-Moore Voting Algorithm works by iterating through the array and maintaining two variables:
  1. Candidate: The potential majority element.
  2. Count: A counter to track how many times the candidate appears.
• We iterate through the array:
  • If the current element is the same as the candidate, we increment the count.
  • If the current element is different from the candidate, we decrement the count.
  • If the count reaches zero, we change the candidate to the current element and reset the count to 1.

After the first pass, the candidate might be the majority element. However, we need a second pass to confirm if it is actually the majority element by counting its occurrences and checking if it appears more than n / 2 times.

Algorithm:

1. First pass: Find the potential candidate for the majority element.
2. Second pass: Verify if the candidate occurs more than n / 2 times.

Code Implementation:

public class Solution {
    public int MajorityElement(int[] arr) {
        int n = arr.Length;
        
        // Step 1: Boyer-Moore Voting Algorithm
        int candidate = -1, count = 0;
        
        for (int i = 0; i < n; i++) {
            if (count == 0) {
                candidate = arr[i];
                count = 1;
            } else if (arr[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        // Step 2: Verify if the candidate is the majority element
        int occurrences = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == candidate) {
                occurrences++;
            }
        }
        
        if (occurrences > n / 2) {
            return candidate;
        }
        
        return -1;  // No majority element
    }
}

Explanation:

1. First Pass (Boyer-Moore Voting Algorithm):

   • We iterate through the array and maintain a candidate and a count.
   • If the current element matches the candidate, increment the count.
   • If it doesn't match, decrement the count.
   • When the count becomes zero, we update the candidate to the current element and reset count to 1.

2. Second Pass (Verification):

   • After the first pass, the candidate might be the majority element. To confirm, we count how many times the candidate appears in the array.
   • If it appears more than n / 2 times, return the candidate as the majority element.
   • If it doesn't, return -1 indicating no majority element exists.

Time Complexity:

• Time Complexity: $O(n)$, where n is the size of the array. We perform two passes over the array (one for finding the candidate and one for verifying).
• Space Complexity: $O(1)$, since we are only using a constant amount of extra space.

Example Walkthrough:

Example 1:

• Input: arr[] = [3, 1, 3, 3, 2]
• First Pass:
  • Start with candidate = -1 and count = 0.
  • The first element 3 sets the candidate to 3 and count = 1.
  • The second element 1 decreases the count to 0, and the candidate is updated to 1.
  • The third element 3 sets the candidate to 3 and count = 1.
  • The fourth element 3 increments count to 2.
  • The fifth element 2 decreases count to 1.
  • After the first pass, the candidate is 3.
• Second Pass:
  • Count the occurrences of 3, which appears 3 times.
  • Since 3 appears more than n / 2 times (3 out of 5), return 3.

Output: 3

Example 2:

• Input: arr[] = [2, 13]
• First Pass:
  • The candidate will be either 2 or 13 depending on the iteration, but neither will appear more than once.
• Second Pass:
  • No element appears more than n / 2 times.
• Output: -1

Conclusion:

The Boyer-Moore Voting Algorithm efficiently solves the majority element problem with a time complexity of $O(n)$ and space complexity of $O(1)$. This makes it an optimal solution for large arrays with constraints up to $10^5$.

Geeksforgeeks: Kth Smallest

 Kth Smallest

Difficulty: Medium

Given an array arr[] and an integer k where k is smaller than the size of the array, the task is to find the kth smallest element in the given array.

Follow up: Don't solve it using the inbuilt sort function.

Examples :

Input: arr[] = [7, 10, 4, 3, 20, 15], k = 3
Output:  7
Explanation: 3rd smallest element in the given array is 7.

Input: arr[] = [2, 3, 1, 20, 15], k = 4 
Output: 15
Explanation: 4th smallest element in the given array is 15.

Expected Time Complexity: O(n+(max_element) )

Expected Auxiliary Space: O(max_element)

Constraints:
1 <= arr.size <= 106
1<= arr[i] <= 106
1 <= k <= n

To solve the problem of finding the kth smallest element in an array without using built-in sorting functions, we can use a heap-based approach, particularly min-heap or max-heap.

Approach:

1. Min-Heap Approach:

   • We can build a min-heap of size k.
   • Then, for each element in the array:
     • If the heap size is less than k, we push the element into the heap.
     • If the heap size exceeds k, we pop the minimum element from the heap.
   • After processing all elements, the root of the heap will contain the kth smallest element.
   • Time complexity: The heap operations (insert and delete-min) take $O(\log k)$, and we do this for $n$ elements, so the overall time complexity is $O(n \log k)$.

2. Counting Sort Approach (For a restricted range of values):

   • Given the problem constraints, we can also solve this using a counting sort-like approach. We count the frequency of each element and iterate through the frequencies to find the kth smallest.
   • Time complexity: This approach runs in $O(n + M)$, where $M$ is the maximum value in the array. However, this approach may not be feasible if the maximum value in the array is too large.

Solution using Min-Heap Approach in C#:

using System;
using System.Collections.Generic;

public class Solution {
    public int KthSmallest(int[] arr, int k) {
        // Step 1: Create a max-heap with size k
        PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>();

        // Step 2: Insert first k elements into the heap
        for (int i = 0; i < k; i++) {
            maxHeap.Enqueue(arr[i], -arr[i]);  // We use -arr[i] to simulate max-heap (since PriorityQueue is min-heap by default)
        }

        // Step 3: Process the remaining elements
        for (int i = k; i < arr.Length; i++) {
            if (arr[i] < -maxHeap.Peek()) {  // Compare with the root of the heap
                maxHeap.Dequeue();           // Remove the largest element in the heap
                maxHeap.Enqueue(arr[i], -arr[i]);  // Add the new smaller element
            }
        }

        // Step 4: The root of the heap is the kth smallest element
        return -maxHeap.Peek();
    }
}

// Driver code to test
public class Program {
    public static void Main(string[] args) {
        Solution sol = new Solution();

        int[] arr1 = { 7, 10, 4, 3, 20, 15 };
        int k1 = 3;
        Console.WriteLine("The 3rd smallest element is: " + sol.KthSmallest(arr1, k1));  // Output: 7

        int[] arr2 = { 2, 3, 1, 20, 15 };
        int k2 = 4;
        Console.WriteLine("The 4th smallest element is: " + sol.KthSmallest(arr2, k2));  // Output: 15
    }
}

Explanation:

1. PriorityQueue:

   • A max-heap is implemented using a PriorityQueue in C# (which is a min-heap by default, so we use negative values to simulate the max-heap behavior).

2. First k elements:

   • We add the first k elements to the heap.

3. Remaining elements:

   • For each element from k onwards, we check if it is smaller than the root of the heap (i.e., the largest of the k smallest elements).
   • If so, we remove the largest element from the heap and add the current element to the heap.

4. Result:

   • After processing all elements, the root of the heap will be the kth smallest element.

Time and Space Complexity:

• Time Complexity:
  • Building the heap initially takes $O(k \log k)$.
  • For each of the remaining $n - k$ elements, we perform a heap operation, which takes $O(\log k)$. Therefore, the total time complexity is $O(n \log k)$.
• Space Complexity:
  • The space complexity is $O(k)$, due to the heap storing up to k elements.

Example Walkthrough:

Example 1:

• Input: arr[] = [7, 10, 4, 3, 20, 15], k = 3
• First, we build the heap with the first 3 elements: [7, 10, 4] (max-heap).
• Then we process the remaining elements:
  • For 3: it's smaller than the root (10), so replace 10 with 3. Heap becomes [7, 3, 4].
  • For 20: it's larger than the root (7), so no change.
  • For 15: it's larger than the root (7), so no change.
• The root of the heap is 7, which is the 3rd smallest element.

Example 2:

• Input: arr[] = [2, 3, 1, 20, 15], k = 4
• After building the heap with the first 4 elements: [2, 3, 1, 20].
• Then we process the remaining element 15, and since 15 is smaller than 20, we replace 20 with 15.
• The root of the heap is 15, which is the 4th smallest element.

Conclusion:

This solution efficiently solves the problem of finding the kth smallest element using a max-heap of size k. The time complexity is optimal for the problem, making it suitable for large arrays with constraints up to $10^6$.

For the kth smallest element problem, I've covered the heap-based approach, which is an efficient solution. However, here are a few other approaches that can be considered, along with their time complexities:

1. Sorting Approach (Using Sorting)

• Method: Sort the array in non-decreasing order and pick the element at index k-1.
• Time Complexity: $O(n \log n)$ (due to sorting).
• Space Complexity: $O(1)$ (if sorting in place).

This is the simplest approach but not the most efficient when compared to the heap-based solution.

using System;

public class Solution {
    public int KthSmallest(int[] arr, int k) {
        Array.Sort(arr);
        return arr[k - 1];
    }
}

2. QuickSelect (Partition-based approach)

• Method: Use the QuickSelect algorithm, a variation of QuickSort, to find the kth smallest element. This is more efficient on average than sorting because it doesn't need to fully sort the array.
• Time Complexity: Average case $O(n)$, Worst case $O(n^2)$ (similar to QuickSort).
• Space Complexity: $O(1)$.

QuickSelect works by partitioning the array, much like in QuickSort. Instead of sorting both sides, it continues searching in the side that contains the kth smallest element.

using System;

public class Solution {
    public int KthSmallest(int[] arr, int k) {
        return QuickSelect(arr, 0, arr.Length - 1, k - 1);
    }

    private int QuickSelect(int[] arr, int left, int right, int k) {
        if (left == right) return arr[left];

        int pivotIndex = Partition(arr, left, right);
        if (k == pivotIndex) return arr[k];
        else if (k < pivotIndex) return QuickSelect(arr, left, pivotIndex - 1, k);
        else return QuickSelect(arr, pivotIndex + 1, right, k);
    }

    private int Partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                Swap(arr, i, j);
                i++;
            }
        }
        Swap(arr, i, right);
        return i;
    }

    private void Swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3. Heap-based Approach (as explained previously)

• Method: Use a min-heap or max-heap to efficiently find the kth smallest element.
• Time Complexity: $O(n \log k)$ (for inserting elements into the heap).
• Space Complexity: $O(k)$ (for the heap).

As described earlier, we can use a max-heap to track the k smallest elements, and the root of the heap will give us the kth smallest element.

4. Counting Sort (For a Restricted Range)

• Method: Count the frequency of each element in the array and use that to determine the kth smallest element.
• Time Complexity: $O(n + M)$, where $M$ is the maximum value in the array (or range of values).
• Space Complexity: $O(M)$ for storing the count.

This approach works well when the range of elements is small (for example, if the values are integers between 1 and 100). For larger ranges, this approach might not be feasible.

using System;

public class Solution {
    public int KthSmallest(int[] arr, int k) {
        int maxVal = 0;
        foreach (var num in arr) {
            maxVal = Math.Max(maxVal, num);
        }

        int[] count = new int[maxVal + 1];
        foreach (var num in arr) {
            count[num]++;
        }

        int countSoFar = 0;
        for (int i = 0; i <= maxVal; i++) {
            countSoFar += count[i];
            if (countSoFar >= k) {
                return i;
            }
        }

        return -1; // If no such element exists
    }
}

Conclusion:

For each problem, it's good practice to consider multiple approaches and choose the one that best suits the problem's constraints, especially for large datasets:

1. Sorting is simple but slower for large arrays.
2. QuickSelect is more efficient for average cases but has a worst-case time complexity.
3. Heap-based approaches work well when k is small relative to n.
4. Counting Sort is useful when the range of numbers is constrained.