Geeksforgeeks: Longest Consecutive Subsequence

 Longest Consecutive Subsequence

Difficulty: Medium

Given an array arr[] of non-negative integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

Examples:

Input: arr[] = [2, 6, 1, 9, 4, 5, 3]
Output: 6
Explanation: The consecutive numbers here are 1, 2, 3, 4, 5, 6. These 6 numbers form the longest consecutive subsquence.

Input: arr[] = [1, 9, 3, 10, 4, 20, 2]
Output: 4
Explanation: 1, 2, 3, 4 is the longest consecutive subsequence.

Input: arr[] = [15, 13, 12, 14, 11, 10, 9]
Output: 7
Explanation: The longest consecutive subsequence is 9, 10, 11, 12, 13, 14, 15, which has a length of 7.

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

To solve the problem of finding the length of the longest subsequence of consecutive integers, we can approach it using hashing for efficient lookup.

Approach:

1. Use a Set for Efficient Lookup:

   • First, we can store all elements in a set (or hash table) to allow for O(1) time complexity for checking the presence of elements.

2. Iterate Over the Array:

   • For each element in the array, we check if it is the start of a possible subsequence. If it is, we continue to check for consecutive elements (i.e., element + 1, element + 2, etc.).

3. Track the Maximum Length:

   • For each potential subsequence, we track the length and update the maximum length found.

4. Optimization:

   • Once an element has been part of a subsequence, we can skip further checks for that element by removing it from the set or marking it as visited.

Algorithm:

1. Convert the array into a set to ensure O(1) lookups.
2. For each element, if it is the start of a subsequence (i.e., element - 1 is not in the set), we count the length of the subsequence by checking for element + 1, element + 2, etc.
3. Track the maximum subsequence length during this process.

Code Implementation (C#):

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestConsecutiveSubsequence(int[] arr) {
        HashSet<int> set = new HashSet<int>();
        
        // Add all elements to the set
        foreach (int num in arr) {
            set.Add(num);
        }
        
        int maxLength = 0;
        
        foreach (int num in arr) {
            // Check if it's the start of a subsequence
            if (!set.Contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;
                
                // Count the length of the consecutive subsequence
                while (set.Contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }
                
                // Update the maximum length
                maxLength = Math.Max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        
        // Test Case 1
        int[] arr1 = { 2, 6, 1, 9, 4, 5, 3 };
        Console.WriteLine(solution.LongestConsecutiveSubsequence(arr1));  // Output: 6
        
        // Test Case 2
        int[] arr2 = { 1, 9, 3, 10, 4, 20, 2 };
        Console.WriteLine(solution.LongestConsecutiveSubsequence(arr2));  // Output: 4
        
        // Test Case 3
        int[] arr3 = { 15, 13, 12, 14, 11, 10, 9 };
        Console.WriteLine(solution.LongestConsecutiveSubsequence(arr3));  // Output: 7
    }
}

Explanation:

1. Set Creation:

   • We first create a HashSet to store all elements from the input array, ensuring that we can check the presence of elements in O(1) time.

2. Main Loop:

   • For each element num in the array:
     • We check if num - 1 exists in the set. If it doesn't, this means that num is the starting element of a possible subsequence.
     • We then continue to check for consecutive elements (num + 1, num + 2, etc.), counting the length of this subsequence.

3. Tracking Maximum Length:

   • The length of each consecutive subsequence is compared to the current maximum length, and we update the maximum length if a longer subsequence is found.

4. Returning the Result:

   • After all elements are processed, the maximum length of any consecutive subsequence is returned.

Time and Space Complexity:

• Time Complexity:
  • Constructing the set takes $O(n)$, where $n$ is the size of the array.
  • For each element, we may need to check the consecutive numbers. However, each element is processed at most once, making the total time complexity $O(n)$.
• Space Complexity:
  • The space complexity is $O(n)$ due to the set storing all the elements.

Edge Cases:

1. Empty Array:

   • If the array is empty, the result should be 0 because there are no subsequences.

2. All Elements Are Same:

   • If all elements are the same, the longest subsequence is the element itself, with a length of 1.

3. Array with No Consecutive Numbers:

   • If the array contains no consecutive numbers, the longest subsequence will have a length of 1.

Examples:

1. Input: arr = [2, 6, 1, 9, 4, 5, 3]

   • Output: 6 (The longest consecutive subsequence is [1, 2, 3, 4, 5, 6])

2. Input: arr = [1, 9, 3, 10, 4, 20, 2]

   • Output: 4 (The longest consecutive subsequence is [1, 2, 3, 4])

3. Input: arr = [15, 13, 12, 14, 11, 10, 9]

   • Output: 7 (The longest consecutive subsequence is [9, 10, 11, 12, 13, 14, 15])

This solution efficiently finds the longest consecutive subsequence using hashing with a time complexity of $O(n)$, which is well-suited for large input sizes.

Geeksforgeeks: Undirected Graph Cycle

 Undirected Graph Cycle

Difficulty: Medium

Given an undirected graph with V vertices labelled from 0 to V-1 and E edges, check whether the graph contains any cycle or not. The Graph is represented as an adjacency list, where adj[i] contains all the vertices that are directly connected to vertex i.

NOTE: The adjacency list represents undirected edges, meaning that if there is an edge between vertex i and vertex j, both j will be adj[i] and i will be in adj[j].

Examples:

Input: adj = [[1], [0,2,4], [1,3], [2,4], [1,3]] 
Output: 1
Explanation: 

1->2->3->4->1 is a cycle.

Input: adj = [[], [2], [1,3], [2]]
Output: 0
Explanation: 

No cycle in the graph.

Constraints:
1 ≤ adj.size() ≤ 105

To solve the problem of detecting cycles in an undirected graph, we can utilize a Depth First Search (DFS) approach. Here's how we can approach this problem:

Approach:

1. DFS Traversal:

   • We can traverse the graph using DFS. During the traversal, we'll keep track of visited vertices and the parent of each vertex (the vertex from which we arrived).
   • For each vertex, we check its adjacent vertices:
     • If an adjacent vertex is not visited, we recursively explore it.
     • If an adjacent vertex is already visited and is not the parent of the current vertex, it means we've encountered a cycle.

2. Parent Tracking:

   • The parent tracking is necessary because in an undirected graph, we would otherwise falsely detect a cycle when traversing back to the vertex from which we came.

3. Edge Case:

   • If the graph is disconnected, we need to perform DFS from all unvisited vertices to ensure every component is checked.

Code Implementation (C#):

using System;
using System.Collections.Generic;

public class Solution {
    // Helper function to perform DFS and detect cycle
    private bool DFS(int v, int parent, List<List<int>> adj, bool[] visited) {
        visited[v] = true;
        
        foreach (int neighbor in adj[v]) {
            // If neighbor is not visited, explore it recursively
            if (!visited[neighbor]) {
                if (DFS(neighbor, v, adj, visited)) {
                    return true; // cycle detected
                }
            }
            // If neighbor is visited and is not the parent, cycle is detected
            else if (neighbor != parent) {
                return true;
            }
        }
        
        return false;
    }
    
    public int ContainsCycle(List<List<int>> adj) {
        int V = adj.Count;
        bool[] visited = new bool[V];
        
        // Perform DFS for every unvisited vertex
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (DFS(i, -1, adj, visited)) {
                    return 1; // cycle found
                }
            }
        }
        
        return 0; // no cycle found
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        
        // Example 1: Graph with a cycle
        var adj1 = new List<List<int>> {
            new List<int> { 1 },
            new List<int> { 0, 2, 4 },
            new List<int> { 1, 3 },
            new List<int> { 2, 4 },
            new List<int> { 1, 3 }
        };
        Console.WriteLine(solution.ContainsCycle(adj1));  // Output: 1 (Cycle exists)
        
        // Example 2: Graph without a cycle
        var adj2 = new List<List<int>> {
            new List<int> { },
            new List<int> { 2 },
            new List<int> { 1, 3 },
            new List<int> { 2 }
        };
        Console.WriteLine(solution.ContainsCycle(adj2));  // Output: 0 (No cycle)
    }
}

Explanation of the Code:

1. DFS Function:

   • The DFS function explores the graph recursively:

     • The v parameter represents the current vertex.
     • The parent parameter is the vertex from which we came to the current vertex.
     • The adj parameter is the adjacency list representing the graph.
     • The visited array keeps track of which vertices have been visited.

   • We mark the current vertex v as visited.

   • For each neighboring vertex, we check:

     • If the neighbor is not visited, we recursively perform DFS on that neighbor.
     • If the neighbor is visited and it's not the parent, it means we've encountered a cycle.

2. ContainsCycle Function:

   • The ContainsCycle function initializes the visited array and performs DFS for each unvisited vertex. If a cycle is found during any DFS call, it returns 1, otherwise 0.

3. Graph Input:

   • The graph is represented as an adjacency list, which is a list of lists where each index represents a vertex and contains a list of vertices that are adjacent to it.

Time and Space Complexity:

• Time Complexity: $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges. In the worst case, we visit each vertex and each edge once.

• Space Complexity: $O(V)$, where $V$ is the number of vertices. We use an array to track visited vertices and recursion stack for DFS.

Edge Cases:

1. Graph with no edges (empty graph):
   • If the graph has no edges, it doesn't contain a cycle. The output will be 0.
2. Disconnected graph:
   • If the graph is disconnected, we perform DFS starting from every unvisited vertex to ensure we check all components.

Examples:

1. Input: adj = [[1], [0,2,4], [1,3], [2,4], [1,3]]

   • Output: 1 (There is a cycle: 1 → 2 → 3 → 4 → 1)

2. Input: adj = [[], [2], [1,3], [2]]

   • Output: 0 (No cycle, it's a tree)

This approach efficiently checks for cycles in an undirected graph using DFS with a time complexity of $O(V + E)$.

credits: GeeksforGeeks

Geeksforgeeks: Longest Subarray with Sum K

 Longest Subarray with Sum K

Difficulty: Medium

Given an array arr[] containing integers and an integer k, your task is to find the length of the longest subarray where the sum of its elements is equal to the given value k. If there is no subarray with sum equal to k, return 0.

Examples:

Input: arr[] = [10, 5, 2, 7, 1, -10], k = 15
Output: 6
Explanation: Subarrays with sum = 15 are [5, 2, 7, 1], [10, 5] and [10, 5, 2, 7, 1, -10]. The length of the longest subarray with a sum of 15 is 6.

Input: arr[] = [-5, 8, -14, 2, 4, 12], k = -5
Output: 5
Explanation: Only subarray with sum = 15 is [-5, 8, -14, 2, 4] of length 5.

Input: arr[] = [10, -10, 20, 30], k = 5
Output: 0
Explanation: No subarray with sum = 5 is present in arr[].

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

To solve the problem of finding the length of the longest subarray with a sum equal to a given value k, we can use a hash map (or dictionary) to track the cumulative sum of elements as we traverse the array. This approach allows us to efficiently find the required subarray in O(n) time.

Approach:

1. Cumulative Sum (Prefix Sum):

   • As we iterate through the array, we keep a running sum of the elements.
   • For each element, we check if the difference between the current sum and k has been encountered before in the hash map. If it has, it means there is a subarray whose sum equals k.
   • We also store the first occurrence of each cumulative sum to maximize the length of the subarray when we find a match.

2. Hash Map:

   • The key in the hash map is the cumulative sum, and the value is the first index at which that cumulative sum occurs.
   • If we encounter a cumulative sum that has been seen before, the subarray between the current index and the first occurrence of that cumulative sum has a sum equal to k.

Detailed Steps:

• Initialize the cumulative sum to 0.
• Iterate through the array, updating the cumulative sum.
• For each cumulative sum, check if the difference between the cumulative sum and k exists in the hash map.
  • If it does, calculate the length of the subarray.
  • If it doesn’t exist, add the cumulative sum to the hash map with its index.
• Keep track of the maximum length found.

Code Implementation (C#):

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestSubarrayWithSumK(int[] arr, int k) {
        // Dictionary to store the first occurrence of cumulative sum
        Dictionary<int, int> map = new Dictionary<int, int>();
        
        int maxLength = 0;
        int cumulativeSum = 0;
        
        // Iterate through the array
        for (int i = 0; i < arr.Length; i++) {
            cumulativeSum += arr[i];
            
            // Check if cumulative sum is equal to k
            if (cumulativeSum == k) {
                maxLength = i + 1;
            }
            
            // Check if the cumulative sum minus k has been seen before
            if (map.ContainsKey(cumulativeSum - k)) {
                // Update maxLength
                maxLength = Math.Max(maxLength, i - map[cumulativeSum - k]);
            }
            
            // Store the first occurrence of the cumulative sum
            if (!map.ContainsKey(cumulativeSum)) {
                map[cumulativeSum] = i;
            }
        }
        
        return maxLength;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        
        int[] arr1 = { 10, 5, 2, 7, 1, -10 };
        int k1 = 15;
        Console.WriteLine(solution.LongestSubarrayWithSumK(arr1, k1));  // Output: 6
        
        int[] arr2 = { -5, 8, -14, 2, 4, 12 };
        int k2 = -5;
        Console.WriteLine(solution.LongestSubarrayWithSumK(arr2, k2));  // Output: 5
        
        int[] arr3 = { 10, -10, 20, 30 };
        int k3 = 5;
        Console.WriteLine(solution.LongestSubarrayWithSumK(arr3, k3));  // Output: 0
    }
}

Explanation of the Code:

1. Initialize Variables:

   • maxLength: Keeps track of the length of the longest subarray found with sum k.
   • cumulativeSum: The sum of elements from the start of the array to the current index.
   • map: A dictionary that stores the first occurrence of each cumulative sum.

2. Main Logic:

   • For each element in the array, we add it to cumulativeSum.
   • If cumulativeSum equals k, it means the subarray from index 0 to the current index has a sum equal to k.
   • If cumulativeSum - k is found in the dictionary, it means the subarray from the index after the stored index to the current index has a sum equal to k.
   • The length of such a subarray is i - map[cumulativeSum - k], and we update maxLength if this length is greater than the current maxLength.
   • We store the first occurrence of each cumulativeSum to ensure we are always considering the longest subarray.

Time Complexity:

• Time Complexity: $O(n)$, where n is the number of elements in the array. This is because we are iterating through the array once and performing constant-time operations (hash map lookups and updates).
• Space Complexity: $O(n)$, since we are storing up to n unique cumulative sums in the hash map.

Edge Cases:

• If the entire array sums to k, the subarray would be the entire array.
• If no subarray sums to k, the result will be 0.
• The array can contain negative numbers, and the approach still works due to how cumulative sums are calculated and checked.

Examples:

1. Input: arr[] = [10, 5, 2, 7, 1, -10], k = 15

   • Output: 6
   • Subarrays with sum 15 are: [5, 2, 7, 1], [10, 5], and [10, 5, 2, 7, 1, -10].

2. Input: arr[] = [-5, 8, -14, 2, 4, 12], k = -5

   • Output: 5
   • Subarray with sum -5 is: [-5, 8, -14, 2, 4].

3. Input: arr[] = [10, -10, 20, 30], k = 5

   • Output: 0
   • No subarray with sum 5 is present.

This solution efficiently solves the problem with optimal time and space complexity.

Geeksforgeeks: Count Inversions

 Count Inversions

Difficulty: Medium

Given an array of integers arr[]. Find the Inversion Count in the array.
Two elements arr[i] and arr[j] form an inversion if arr[i] > arr[j] and i < j.

Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0.
If an array is sorted in the reverse order then the inversion count is the maximum. 

Examples:

Input: arr[] = [2, 4, 1, 3, 5]
Output: 3
Explanation: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

Input: arr[] = [2, 3, 4, 5, 6]
Output: 0
Explanation: As the sequence is already sorted so there is no inversion count.

Input: arr[] = [10, 10, 10]
Output: 0
Explanation: As all the elements of array are same, so there is no inversion count.

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

The Inversion Count is a key concept in analyzing the sortedness of an array. An inversion is a pair of elements in the array such that the first element is greater than the second one, and the first element appears before the second one in the array.

We can approach the problem using different methods, from brute force to optimized solutions leveraging sorting algorithms. Below are several approaches to solve this problem:

Approach 1: Brute Force Approach

This approach involves checking every possible pair (i, j) where i < j. If arr[i] > arr[j], we count that pair as an inversion.

Code for Brute Force:

using System;

public class Solution {
    public int InversionCount(int[] arr) {
        int count = 0;
        int n = arr.Length;

        // Check every pair of elements
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();

        int[] arr1 = { 2, 4, 1, 3, 5 };
        Console.WriteLine(solution.InversionCount(arr1));  // Output: 3

        int[] arr2 = { 2, 3, 4, 5, 6 };
        Console.WriteLine(solution.InversionCount(arr2));  // Output: 0

        int[] arr3 = { 10, 10, 10 };
        Console.WriteLine(solution.InversionCount(arr3));  // Output: 0
    }
}

Time Complexity:

• Time Complexity: $O(n^2)$, where n is the length of the array. This is because we are using two nested loops to check all pairs of elements.
• Space Complexity: $O(1)$, as we are using a constant amount of extra space.

---

Approach 2: Optimized Approach Using Modified Merge Sort

Merge Sort can be modified to count inversions during the merge step. The idea is that when merging two sorted halves of the array, every time we find an element in the right half that is smaller than an element in the left half, we have found an inversion. The number of such inversions can be determined by how many elements are remaining in the left half (because all those elements are greater than the current element of the right half).

Code for Merge Sort Approach:

using System;

public class Solution {
    public int MergeAndCount(int[] arr, int left, int mid, int right) {
        int count = 0;
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        Array.Copy(arr, left, leftArr, 0, n1);
        Array.Copy(arr, mid + 1, rightArr, 0, n2);

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
                count += (n1 - i);  // All remaining elements in leftArr are greater than rightArr[j]
            }
        }

        while (i < n1) {
            arr[k++] = leftArr[i++];
        }

        while (j < n2) {
            arr[k++] = rightArr[j++];
        }

        return count;
    }

    public int InversionCount(int[] arr, int left, int right) {
        int count = 0;
        if (left < right) {
            int mid = left + (right - left) / 2;

            // Recursively count inversions in the left and right subarrays
            count += InversionCount(arr, left, mid);
            count += InversionCount(arr, mid + 1, right);

            // Count inversions during the merge step
            count += MergeAndCount(arr, left, mid, right);
        }
        return count;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();

        int[] arr1 = { 2, 4, 1, 3, 5 };
        Console.WriteLine(solution.InversionCount(arr1, 0, arr1.Length - 1));  // Output: 3

        int[] arr2 = { 2, 3, 4, 5, 6 };
        Console.WriteLine(solution.InversionCount(arr2, 0, arr2.Length - 1));  // Output: 0

        int[] arr3 = { 10, 10, 10 };
        Console.WriteLine(solution.InversionCount(arr3, 0, arr3.Length - 1));  // Output: 0
    }
}

Time Complexity:

• Time Complexity: $O(n \log n)$, where n is the length of the array. The merge sort algorithm divides the array into two halves, and the merging step takes linear time.
• Space Complexity: $O(n)$, since we need extra space for the temporary arrays used during merging.

---

Approach 3: Using Binary Indexed Tree (BIT) or Fenwick Tree

This is a more advanced approach where we maintain a Binary Indexed Tree (BIT) to keep track of the counts of elements while iterating over the array. For each element in the array, we can query the BIT to get the number of elements that are greater than the current element and appear before it in the array.

Steps:

1. Traverse the array from right to left.
2. For each element arr[i], use the BIT to query how many elements are smaller than arr[i] and update the BIT for arr[i].

This approach is efficient but requires additional data structures.

---

Conclusion

1. Brute Force: Simple but inefficient for large arrays with $O(n^2)$ complexity.
2. Merge Sort: Efficient with $O(n \log n)$ complexity, using a modified merge step to count inversions.
3. Binary Indexed Tree: More advanced, efficient $O(n \log m)$, where $m$ is the maximum element in the array, and uses BIT for querying and updating counts.

For most practical purposes, Merge Sort is the go-to solution due to its balance of simplicity and efficiency.

Geeksforgeeks: Minimize the Heights II

 Minimize the Heights II

Difficulty: Medium

Given an array arr[] denoting heights of N towers and a positive integer K.

For each tower, you must perform exactly one of the following operations exactly once.

• Increase the height of the tower by K
• Decrease the height of the tower by K

Find out the minimum possible difference between the height of the shortest and tallest towers after you have modified each tower.

You can find a slight modification of the problem here.
Note: It is compulsory to increase or decrease the height by K for each tower. After the operation, the resultant array should not contain any negative integers.

Examples :

Input: k = 2, arr[] = {1, 5, 8, 10}
Output: 5
Explanation: The array can be modified as {1+k, 5-k, 8-k, 10-k} = {3, 3, 6, 8}.The difference between the largest and the smallest is 8-3 = 5.

Input: k = 3, arr[] = {3, 9, 12, 16, 20}
Output: 11
Explanation: The array can be modified as {3+k, 9+k, 12-k, 16-k, 20-k} -> {6, 12, 9, 13, 17}.The difference between the largest and the smallest is 17-6 = 11. 

Constraints
1 ≤ k ≤ 107
1 ≤ n ≤ 105
1 ≤ arr[i] ≤ 107

 Here's the problem along with multiple approaches to solve it. Let's walk through each approach for finding the minimum possible difference between the height of the shortest and tallest towers after modifying their heights.

Problem:

Given an array arr[] denoting the heights of N towers and a positive integer K. For each tower, you must either:

• Increase its height by K, or
• Decrease its height by K.

You need to find out the minimum possible difference between the height of the shortest and tallest towers after performing the modification on each tower.

Approaches:

---

Approach 1: Greedy Solution (Sorting + Greedy Adjustment)

1. Sort the Array: Sorting helps because the smallest and largest towers influence the difference. Once sorted, we only need to manipulate the extremes of the array to minimize the difference.
2. Modify the Heights: For each tower, either increase or decrease its height by K and calculate the new difference.
3. Two Possible Configurations:
   • Modify the smallest tower by adding K and the largest tower by subtracting K.
   • Modify the smallest tower by subtracting K and the largest tower by adding K.
4. Calculate the Difference: After modification, compute the new height difference and track the minimum difference.

Code for Approach 1:

using System;

public class Solution {
    public int MinDifference(int[] arr, int k) {
        // Step 1: Sort the array
        Array.Sort(arr);

        // If there is only one tower, no operation can reduce the difference
        if (arr.Length == 1) return 0;

        int n = arr.Length;
        int initialDifference = arr[n - 1] - arr[0];  // Initial difference without any operation

        // Step 2: Start considering the possibilities
        int minDifference = initialDifference;

        for (int i = 0; i < n - 1; i++) {
            int small = Math.Min(arr[0] + k, arr[i + 1] - k);  // Modify the smallest tower or next smallest
            int large = Math.Max(arr[i] + k, arr[n - 1] - k);  // Modify the largest tower or next largest

            // Update the minimum possible difference
            minDifference = Math.Min(minDifference, large - small);
        }

        return minDifference;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        
        int[] arr1 = { 1, 5, 8, 10 };
        int k1 = 2;
        Console.WriteLine(solution.MinDifference(arr1, k1));  // Output: 5

        int[] arr2 = { 3, 9, 12, 16, 20 };
        int k2 = 3;
        Console.WriteLine(solution.MinDifference(arr2, k2));  // Output: 11
    }
}

Time Complexity:

• Sorting the array takes $O(n \log n)$.
• After sorting, the loop runs in $O(n)$, so the overall time complexity is $O(n \log n)$.

Space Complexity:

• The space complexity is $O(1)$ since no additional data structures are used apart from the input array.

---

Approach 2: Brute Force Solution (Exploring All Possibilities)

If you're looking for a simpler but inefficient solution:

1. Try All Possible Combinations: For each tower, try increasing or decreasing its height by K and calculate the difference between the tallest and shortest towers.
2. Find the Minimum Difference: After trying all combinations of modifying the towers, return the smallest difference found.

This approach works but is inefficient for larger arrays due to its exponential nature.

Code for Approach 2:

using System;

public class Solution {
    public int MinDifference(int[] arr, int k) {
        // If the array has only one element, the answer is 0 because no operation is needed
        if (arr.Length == 1) return 0;

        int n = arr.Length;
        int minDifference = int.MaxValue;

        // Explore all possibilities
        for (int i = 0; i < (1 << n); i++) {
            int[] temp = new int[n];
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    temp[j] = arr[j] + k;  // Increase height by K
                } else {
                    temp[j] = arr[j] - k;  // Decrease height by K
                }
            }

            // Find the difference between the largest and smallest heights
            int maxHeight = int.MinValue, minHeight = int.MaxValue;
            for (int j = 0; j < n; j++) {
                maxHeight = Math.Max(maxHeight, temp[j]);
                minHeight = Math.Min(minHeight, temp[j]);
            }

            minDifference = Math.Min(minDifference, maxHeight - minHeight);
        }

        return minDifference;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        
        int[] arr1 = { 1, 5, 8, 10 };
        int k1 = 2;
        Console.WriteLine(solution.MinDifference(arr1, k1));  // Output: 5

        int[] arr2 = { 3, 9, 12, 16, 20 };
        int k2 = 3;
        Console.WriteLine(solution.MinDifference(arr2, k2));  // Output: 11
    }
}

Time Complexity:

• The time complexity is $O(2^n)$, where $n$ is the size of the array. This is due to the need to try all possible combinations of increasing and decreasing each element.

Space Complexity:

• The space complexity is $O(n)$ because we're using an extra array to store the modified heights during the combinations.

---

Approach 3: Optimized Sliding Window (Dynamic Programming Variant)

While the above approaches focus on either sorting or brute force, a more dynamic programming or sliding window approach could optimize the process for large input sizes. You can use this technique to minimize the complexity of the operation but it's harder to achieve with this problem due to the constraints and operations required (increment and decrement).

For large $n$, the greedy approach mentioned in Approach 1 is generally the most efficient.