# DSA: Arrays

Arrays are fundamental data structures in computer science, used to store elements of the same type in a contiguous block of memory. Each element in the array can be accessed using its index, which represents its position in the array. Here's an overview of arrays and their characteristics, including how they are laid out in memory, and the operations commonly supported on them.

Arrays are stored in a continuous memory location. Here’s a simple ASCII art representation of an array layout in memory:

```
+----+----+----+----+----+
| A0 | A1 | A2 | A3 | A4 |
+----+----+----+----+----+
```

**A0, A1, A2, A3, A4**are array elements.Each box represents a memory slot dedicated to an array element.

The array index is often zero-based, meaning the first element is accessed with an index of `0`

.

Arrays support a variety of operations. The most common are:

**Accessing**:Directly access any element with its index.

Time complexity: O(1) (constant time).

**Insertion**:Insert elements at any position.

May require shifting elements to make space for the new element.

Time complexity: O(n) in the worst case, where

`n`

is the number of elements.

**Deletion**:Remove an element from any position.

Requires shifting elements to fill the space created by the removed element.

Time complexity: O(n) in the worst case.

**Searching**:Linear search to find an element by checking every element.

Binary search is possible if the array is sorted, significantly faster (O(log n)).

Time complexity: O(n) for linear search and O(log n) for binary search.

**Updating**:Modify the value of an element at a specific index.

Time complexity: O(1).

**Sorting**:Arrays can be sorted using various algorithms like quicksort, mergesort, bubblesort, etc.

Improves the efficiency of other operations like binary search.

Time complexity varies with the algorithm (commonly O(n log n) for efficient sorts).

**Iterating**:Go through each element, typically for processing or condition checking.

Time complexity: O(n).

**Slicing**(in some languages like Python):Create a new array from a subset of the original array.

Time complexity: O(k) where

`k`

is the number of elements in the slice.

**Merging**:Combine two arrays into a new array.

Often part of more complex operations like mergesort.

Time complexity: O(n + m) where

`n`

and`m`

are the sizes of the arrays.

**Resizing**:Changing the size of the array (more common in dynamic arrays).

Involves creating a new array and copying elements from the old array.

Time complexity: O(n).

Arrays are versatile and efficient for many operations, especially when you need fast access and are working with a fixed number of elements. However, operations that involve shifting elements (like insertion and deletion) can be costly, which leads to the consideration of other data structures like linked lists where these operations can be more efficient.

Below, I'll provide C code snippets for each of the 10 common operations on arrays. These examples assume the use of integer arrays for simplicity.

**1. Accessing an Element**

```
#include <stdio.h>
int main() {
int array[] = {10, 20, 30, 40, 50};
int index = 2; // Accessing the third element (zero-based index)
printf("Element at index %d is %d\n", index, array[index]);
return 0;
}
```

**2. Insertion at a Given Index**

```
#include <stdio.h>
void insert(int arr[], int n, int x, int pos) {
// Shift elements to the right
for (int i = n; i > pos; i--)
arr[i] = arr[i - 1];
arr[pos] = x; // Insert x at pos
}
int main() {
int array[6] = {10, 20, 30, 40, 50};
int x = 25; // Element to insert
int pos = 2; // Position to insert at
insert(array, 5, x, pos);
for (int i = 0; i < 6; i++)
printf("%d ", array[i]);
return 0;
}
```

**3. Deletion at a Given Index**

```
#include <stdio.h>
void delete(int arr[], int n, int pos) {
// Shift elements to the left
for (int i = pos; i < n - 1; i++)
arr[i] = arr[i + 1];
}
int main() {
int array[] = {10, 20, 30, 40, 50};
int pos = 2; // Position to delete from
delete(array, 5, pos);
for (int i = 0; i < 4; i++)
printf("%d ", array[i]);
return 0;
}
```

**4. Searching (Linear Search)**

```
#include <stdio.h>
int search(int arr[], int n, int x) {
for (int i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1; // Element not found
}
int main() {
int array[] = {10, 20, 30, 40, 50};
int x = 30;
int result = search(array, 5, x);
if (result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found\n");
return 0;
}
```

**5. Updating an Element**

```
#include <stdio.h>
int main() {
int array[] = {10, 20, 30, 40, 50};
int index = 3;
array[index] = 100; // Update element at index 3
printf("Updated element at index %d is %d\n", index, array[index]);
return 0;
}
```

**6. Sorting (Bubble Sort)**

```
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
int main() {
int array[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(array)/sizeof(array[0]);
bubbleSort(array, n);
for (int i = 0; i < n; i++)
printf("%d ", array[i]);
return 0;
}
```

**7. Iterating Over Elements**

```
#include <stdio.h>
int main() {
int array[] = {10, 20, 30, 40, 50};
for (int i = 0; i < 5; i++)
printf("Element %d: %d\n", i, array[i]);
return 0;
}
```

**8. Slicing an Array**

```
#include <stdio.h>
void slice(int source[], int start, int end, int dest[]) {
for (int i = start; i < end; i++) {
dest[i - start] = source[i];
}
}
int main() {
int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int result[5]; // Destination array
slice(array, 3, 8, result); // Slice from index 3 to 7
for (int i = 0; i < 5; i++)
printf("%d ", result[i]);
return 0;
}
```

**9. Merging Two Arrays**

```
#include <stdio.h>
void merge(int a[], int b[], int c[], int n, int m) {
for (int i = 0; i < n; i++)
c[i] = a[i];
for (int i = 0; i < m; i++)
c[n + i] = b[i];
}
int main() {
int a[] = {1, 3, 5};
int b[] = {2, 4, 6, 8};
int c[7]; // Array to hold merged result
merge(a, b, c, 3, 4);
for (int i = 0; i < 7; i++)
printf("%d ", c[i]);
return 0;
}
```

**10. Resizing an Array**

In C, resizing an array typically involves allocating a new array of the desired size and copying elements from the old array to the new one, as C does not support dynamic resizing of arrays natively. Here's an example using dynamic memory allocation:

```
#include <stdio.h>
#include <stdlib.h>
int* resize(int* arr, int n, int new_size) {
int* new_arr = (int*) malloc(new_size * sizeof(int));
for (int i = 0; i < n && i < new_size; i++)
new_arr[i] = arr[i];
free(arr); // Free the old array
return new_arr;
}
int main() {
int* array = malloc(5 * sizeof(int)); // Original array
array[0] = 10;
array[1] = 20;
array[2] = 30;
array[3] = 40;
array[4] = 50;
int new_size = 10; // New size of the array
array = resize(array, 5, new_size);
for (int i = 0; i < new_size; i++)
printf("%d ", array[i]); // Printing elements to check
free(array); // Free the resized array
return 0;
}
```

Here's a list of 20 common interview coding questions on arrays, arranged in increasing order of difficulty. These questions are designed to test various aspects of your programming skills, including your ability to manipulate array data structures, implement algorithms, and optimize solutions.

**Beginner Level**

**Find the Largest Element in an Array**- Write a program to find the largest number in a given array.

**Check if the Array Contains a Given Element**- Implement a function that checks whether an array contains a specific value.

**Calculate the Sum of Array Elements**- Write a function to sum all the numbers in an array.

**Reverse an Array**- Develop a method to reverse an array in place without using additional storage.

**Count Even and Odd Numbers**- Given an array of integers, write a program to count the number of even and odd elements in it.

**Intermediate Level**

**Remove Duplicates from a Sorted Array**- Modify the array so that it contains no duplicates, potentially reducing its size.

**Rotate Array to the Right**- Implement a function that rotates the elements of an array to the right by a given number of steps.

**Find All Pairs in Array with a Given Sum**- Design a method to find all pairs of integers within an array which sum to a specified value.

**Merge Two Sorted Arrays**- Merge two sorted arrays into one sorted array.

**Find the "Kth" Max and Min Element of an Array**- Devise an algorithm to find both the kth largest and kth smallest numbers in an array.

**Advanced Level**

**Move Zeroes to the End of the Array**- Given an array of integers, move all the zeroes to the end while maintaining the relative order of the other elements.

**Implement a Circular Queue Using an Array**- Create a circular queue with basic operations like enqueue, dequeue, and display.

**Find the Longest Consecutive Subsequence**- Identify the length of the longest subsequence such that elements in the subsequence are consecutive integers.

**Maximum Product Subarray**- Find the contiguous subarray within an array (containing at least one number) which has the largest product.

**Spiral Order Matrix Traversal**- Given a 2D array, print it in spiral order.

**Expert Level**

**Minimum Swaps to Bring Elements Less Than K Together**- Calculate the minimum number of swaps required to bring all the elements less than or equal to k together.

**First Missing Positive**- Given an unsorted integer array, find the smallest missing positive integer.

**Trapping Rain Water**- Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

**Subarray with Given Sum**- Find a subarray that sums to a given number in an array of non-negative numbers.

**Longest Substring Without Repeating Characters**- Given a string, find the length of the longest substring without repeating characters (applicable to arrays if the string is treated as a character array).

### Hints

**Find the Largest Element in an Array**: Iterate through the array while maintaining a variable to store the maximum value found so far. Update this variable whenever you encounter a larger value.**Check if the Array Contains a Given Element**: Traverse the array from start to end, comparing each element to the target value. Return true as soon as a match is found; if no match is found by the end of the array, return false.**Calculate the Sum of Array Elements**: Initialize a sum variable to zero and iterate through all elements of the array, adding each element to the sum variable. Return the sum after the loop completes.**Reverse an Array**: Use two pointers, one starting at the beginning of the array and the other at the end. Swap the elements at these pointers and then move them towards each other until they meet or cross.**Count Even and Odd Numbers**: As you iterate through the array, use a conditional statement to check if each element is even or odd and increment respective counters based on the result.**Remove Duplicates from a Sorted Array**: Utilize two pointers: one for iterating through the array and another for placing non-duplicate elements. Compare each element with the previous one and copy it to the second pointer's location only if they are different, then increment the second pointer.**Rotate Array to the Right**: To rotate the array without using extra space, first reverse the entire array, then reverse the first k elements, and finally reverse the rest of the array.**Find All Pairs in Array with a Given Sum**: Use a hashmap to store elements as keys and their frequencies as values. For each element, check if the difference between the target sum and the current element exists in the map. If it does, that pair contributes to the target sum.**Merge Two Sorted Arrays**: Utilize a two-pointer technique starting at the beginning of each array. Compare the elements at the pointer locations, append the smaller element to the result, and move the respective pointer. Continue until all elements from both arrays are in the result.**Find the "Kth" Max and Min Element of an Array**: Implement a quick-select algorithm (a variant of quicksort) to find the kth largest or smallest element without fully sorting the array.**Move Zeroes to the End of the Array**: Use a pointer to track the position of the next non-zero element. As you iterate through the array, place each non-zero element at this pointer and increment the pointer, then fill in zeros for the remaining positions.**Implement a Circular Queue Using an Array**: Manage a fixed-size array with two pointers, one for the front and one for the rear. Handle wrap-around of the pointers using modulo arithmetic when enqueuing or dequeuing elements.**Find the Longest Consecutive Subsequence**: Use a HashSet to store all elements of the array, then for each element, check if it is the start of a sequence (i.e., there is no element with value -1 of this element in the set) and then count how many consecutive numbers are present.**Maximum Product Subarray**: Use a dynamic programming approach that keeps track of both the maximum and minimum products up to each index, because the minimum product can become the maximum if the next element in the array is negative.**Spiral Order Matrix Traversal**: Decompose the problem into printing the perimeter of the matrix in a spiral manner, then recursively call the function to print the spiral order of the inner sub-matrix.**Minimum Swaps to Bring Elements Less Than K Together**: Use a sliding window technique to count how many elements greater than k are in each window of size equal to the number of elements less than or equal to k, then find the minimum count of such undesired elements across all windows.**First Missing Positive**: Employ an in-place hashing technique by attempting to place each number in its corresponding index position (i.e., number 1 in index 0, number 2 in index 1, etc.), then the first missing index will give the smallest missing positive.**Trapping Rain Water**: Calculate the maximum height of bars on the left and right of every bar using two arrays. The amount of water on top of each bar is the minimum of maximum heights minus the height of the bar itself.**Subarray with Given Sum**: For an array of non-negative numbers, use a sliding window or two-pointer approach to find the subarray that sums to the target value, adjusting the window size by moving the pointers based on the current sum.**Longest Substring Without Repeating Characters**: Utilize a sliding window along with a hashmap that stores characters and their indices. Move the start of the window forward to skip the repeated character when a duplicate is found, maintaining the maximum length of the window.

### Solutions

**1. Find the Largest Number in an Array**

This program will find the largest number in a given array.

```
#include <stdio.h>
// Function to find the largest number in an array
int findLargest(int arr[], int size) {
int max = arr[0]; // Assume the first element is the largest initially
for (int i = 1; i < size; i++) {
if (arr[i] > max) { // If we find a larger number
max = arr[i]; // Update max
}
}
return max; // Return the largest number
}
int main() {
int numbers[] = {3, 5, 9, 1, 6}; // Example array
int size = sizeof(numbers) / sizeof(numbers[0]); // Calculate array size
printf("The largest number is: %d\n", findLargest(numbers, size));
return 0;
}
```

**Explanation with example:**

Assume we have the array `{3, 5, 9, 1, 6}`

.

```
Initial array:
+---+---+---+---+---+
| 3 | 5 | 9 | 1 | 6 |
+---+---+---+---+---+
^ Initial max
```

**Step-by-Step Execution:**

**Initial max:**`max = 3`

**Iteration 1:**Compare 5 with max (3).5 is greater than 3.

Update max to 5.

```
Current max = 5
+---+---+---+---+---+
| 3 | 5 | 9 | 1 | 6 |
+---+---+---+---+---+
^ Current max
```

**Iteration 2:**Compare 9 with max (5).9 is greater than 5.

Update max to 9.

```
Current max = 9
+---+---+---+---+---+
| 3 | 5 | 9 | 1 | 6 |
+---+---+---+---+---+
^ Current max
```

**Iteration 3:**Compare 1 with max (9).1 is not greater than 9.

No update.

**Iteration 4:**Compare 6 with max (9).6 is not greater than 9.

No update.

```
Final max = 9
+---+---+---+---+---+
| 3 | 5 | 9 | 1 | 6 |
+---+---+---+---+---+
^ Final max
```

**Output:** "The largest number is: 9"

**2. Check If an Array Contains a Specific Value**

This function checks whether an array contains a specific value.

```
#include <stdio.h>
#include <stdbool.h> // Include to use bool in C
// Function to check if an array contains a specific value
bool contains(int arr[], int size, int value) {
for (int i = 0; i < size; i++) {
if (arr[i] == value) { // If the current element is the value we're looking for
return true; // Return true
}
}
return false; // If not found, return false
}
int main() {
int numbers[] = {7, 2, 8, 4, 6};
int size = sizeof(numbers) / sizeof(numbers[0]);
int value = 4;
printf("Array contains %d: %s\n", value, contains(numbers, size, value) ? "Yes" : "No");
return 0;
}
```

**3. Sum All Numbers in an Array**

This function sums all the numbers in an array.

```
#include <stdio.h>
// Function to sum all numbers in an array
int sumArray(int arr[], int size) {
int total = 0; // Initialize sum to zero
for (int i = 0; i < size; i++) {
total += arr[i]; // Add each element to total
}
return total; // Return the sum
}
int main() {
int numbers[] = {5, 9, 1, 3, 2};
int size = sizeof(numbers) / sizeof(numbers[0]);
printf("Total sum is: %d\n", sumArray(numbers, size));
return 0;
}
```

**4. Reverse an Array In-place**

This method reverses an array in place without using additional storage.

```
#include <stdio.h>
// Function to reverse an array in place
void reverseArray(int arr[], int size) {
for (int i = 0; i < size / 2; i++) {
int temp = arr[i]; // Temporary variable to store the element
arr[i] = arr[size - i - 1]; // Swap elements
arr[size - i - 1] = temp; // Continue swapping
}
}
int main() {
int numbers[] = {1, 2, 3, 4, 5};
int size = sizeof(numbers) / sizeof(numbers[0]);
reverseArray(numbers, size);
printf("Reversed array: ");
for (int i = 0; i < size; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
return 0;
}
```

**Explanation with example:**

Assume we have the array `{1, 2, 3, 4, 5}`

.

```
Initial array:
+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+
```

**Step-by-Step Execution:**

**Iteration 0:**Swap index 0 (value 1) with index 4 (value 5).

```
+---+---+---+---+---+
| 5 | 2 | 3 | 4 | 1 |
+---+---+---+---+---+
^ ^
```

**Iteration 1:**Swap index 1 (value 2) with index 3 (value 4).

```
+---+---+---+---+---+
| 5 | 4 | 3 | 2 | 1 |
+---+---+---+---+---+
^ ^
```

**Iteration 2:**The loop ends because the array size divided by 2 gives 2, which means only the first two pairs need swapping.

**Reversed Array Output:**

```
array: 5 4 3 2 1
```

**5. Count Even and Odd Numbers**

This program counts the number of even and odd numbers in an array.

```
#include <stdio.h>
// Function to count even and odd numbers
void countEvenOdd(int arr[], int size, int *evenCount, int *oddCount) {
*evenCount = 0; // Initialize even count
*oddCount = 0; // Initialize odd count
for (int i = 0; i < size; i++) {
if (arr[i] % 2 == 0) { // Check if the number is even
(*evenCount)++; // Increment even count
} else { // Otherwise, it's odd
(*oddCount)++; // Increment odd count
}
}
}
int main() {
int numbers[] = {10, 23, 22, 15, 9};
int size = sizeof(numbers) / sizeof(numbers
[0]);
int evenCount, oddCount;
countEvenOdd(numbers, size, &evenCount, &oddCount);
printf("Even count: %d, Odd count: %d\n", evenCount, oddCount);
return 0;
}
```

**6. Remove Duplicates from a Sorted Array**

This function will modify the array to remove duplicates and return the new length of the array without duplicates.

```
#include <stdio.h>
// Function to remove duplicates from a sorted array
int removeDuplicates(int arr[], int size) {
if (size == 0) return 0; // If array is empty, return 0
int j = 0; // This will be the index for the new length of the array
for (int i = 1; i < size; i++) {
if (arr[j] != arr[i]) { // If current element is not equal to the last unique element
j++; // Move to next position
arr[j] = arr[i]; // Set it as the next unique element
}
}
return j + 1; // Return the new length of the array without duplicates
}
int main() {
int numbers[] = {1, 1, 2, 2, 3, 4, 4, 5, 5};
int size = sizeof(numbers) / sizeof(numbers[0]);
int newSize = removeDuplicates(numbers, size);
printf("Array after removing duplicates: ");
for (int i = 0; i < newSize; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
return 0;
}
```

**Explanation with example:**

Assume we have the array `{1, 1, 2, 2, 3, 4, 4, 5, 5}`

.

```
Initial array:
+---+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 2 | 3 | 4 | 4 | 5 | 5 |
+---+---+---+---+---+---+---+---+---+
```

**Step-by-Step Execution:**

**Initial Setup:**Start with`j = 0`

.`arr[j]`

is`1`

.

**Iterations:**

**i = 1:**`arr[1]`

is`1`

. No change since it's a duplicate.**i = 2:**`arr[2]`

is`2`

. It's different from`arr[j]`

(which is`1`

).Increment

`j`

to`1`

.Update

`arr[1]`

to`2`

.

**i = 3:**`arr[3]`

is`2`

. No change since it's a duplicate.**i = 4:**`arr[4]`

is`3`

. Different from`arr[j]`

(which is`2`

).Increment

`j`

to`2`

.Update

`arr[2]`

to`3`

.

**i = 5:**`arr[5]`

is`4`

. Different from`arr[j]`

(which is`3`

).Increment

`j`

to`3`

.Update

`arr[3]`

to`4`

.

**i = 6:**`arr[6]`

is`4`

. No change since it's a duplicate.**i = 7:**`arr[7]`

is`5`

. Different from`arr[j]`

(which is`4`

).Increment

`j`

to`4`

.Update

`arr[4]`

to`5`

.

**i = 8:**`arr[8]`

is`5`

. No change since it's a duplicate.

**Final Array and Output:**

```
New array (after removing duplicates):
+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+
```

**7. Rotate Array to the Right**

This function will rotate an array to the right by a certain number of steps.

```
#include <stdio.h>
// Function to reverse a portion of the array from 'start' to 'end'
void reverse(int arr[], int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// Function to rotate the array right by 'k' positions
void rotateRight(int arr[], int size, int k) {
if (size == 0) return;
k = k % size; // In case the number of rotations is greater than the array size
if (k == 0) return; // If k is 0, no rotation is needed
// Step 1: Reverse the entire array
reverse(arr, 0, size - 1);
// Step 2: Reverse the first k elements
reverse(arr, 0, k - 1);
// Step 3: Reverse the remaining elements
reverse(arr, k, size - 1);
}
int main() {
int numbers[] = {1, 2, 3, 4, 5, 6, 7};
int size = sizeof(numbers) / sizeof(numbers[0]);
int k = 3; // Number of positions to rotate the array to the right
printf("Original array: ");
for (int i = 0; i < size; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
rotateRight(numbers, size, k);
printf("Rotated array: ");
for (int i = 0; i < size; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
return 0;
}
```

**Explanation with example:**

Let's start with the array and try to rotate it by 3 to the right.

```
Initial array:
+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+
```

**Step 1: Reverse the entire array**

Reverse the whole array without any condition. Here’s how the array looks after each swap:

Swap

`1`

and`7`

Swap

`2`

and`6`

Swap

`3`

and`5`

```
Array after reversing entirely:
+---+---+---+---+---+---+---+
| 7 | 6 | 5 | 4 | 3 | 2 | 1 |
+---+---+---+---+---+---+---+
```

**Step 2: Reverse the first k elements**

Now, reverse the first `k`

elements where `k = 3`

. This part only involves the elements `7`

, `6`

, and `5`

.

- Swap
`7`

and`5`

```
Array after reversing the first 3 elements:
+---+---+---+---+---+---+---+
| 5 | 6 | 7 | 4 | 3 | 2 | 1 |
+---+---+---+---+---+---+---+
```

**Step 3: Reverse the rest of the array**

Finally, reverse the rest of the array after the first `k`

elements:

Swap

`4`

and`1`

Swap

`3`

and`2`

```
Array after reversing the rest:
+---+---+---+---+---+---+---+
| 5 | 6 | 7 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+
```

**8. Find All Pairs in Array with a Given Sum**

This function finds all pairs in the array that add up to a specific sum.

```
#include <stdio.h>
#include <stdlib.h>
// Comparator function for qsort
int compare(const void *a, const void *b) {
int int_a = *((int*)a);
int int_b = *((int*)b);
return int_a - int_b;
}
// Function to find all pairs in the array that sum to a specific value
void findPairs(int arr[], int size, int sum) {
// First, sort the array
qsort(arr, size, sizeof(int), compare);
int left = 0; // Start pointer
int right = size - 1; // End pointer
while (left < right) {
int currentSum = arr[left] + arr[right];
if (currentSum == sum) { // Check if the current sum matches the desired sum
printf("(%d, %d)\n", arr[left], arr[right]);
left++;
right--;
} else if (currentSum < sum) {
left++; // Move the left pointer to the right to increase the sum
} else {
right--; // Move the right pointer to the left to decrease the sum
}
}
}
int main() {
int numbers[] = {1, 5, 3, 7, 9, 2, 6, 4, 8};
int size = sizeof(numbers) / sizeof(numbers[0]);
int sum = 10;
printf("Pairs in the array that sum to %d are:\n", sum);
findPairs(numbers, size, sum);
return 0;
}
```

**Explanation with example:**

**1. Initial Array**

The initial unsorted array is:

```
+---+---+---+---+---+---+---+---+---+
| 1 | 5 | 3 | 7 | 9 | 2 | 6 | 4 | 8 |
+---+---+---+---+---+---+---+---+---+
```

**2. Sorting the Array**

First, the array is sorted using `qsort`

, which applies a quicksort algorithm. The sorted array becomes:

```
+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+
```

**3. Setting Up Two Pointers**

`left`

pointer starts at the first element.`right`

pointer starts at the last element.

```
+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+
^ ^
left right
```

**4. Finding Pairs with Sum = 10**

We'll now use the two-pointer technique to find pairs that sum to `10`

.

**Iteration 1:**`sum = 1 + 9 = 10`

Found pair:

`(1, 9)`

Move both pointers inward.

```
+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+-------+---+---+---+---+---+-------+
^ ^
left right
```

**Iteration 2:**`sum = 2 + 8 = 10`

Found pair:

`(2, 8)`

Move both pointers inward.

```
+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+-------+---+---+---+---+---+-------+
^ ^
left right
```

**Iteration 3:**`sum = 3 + 7 = 10`

Found pair:

`(3, 7)`

Move both pointers inward.

```
+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+-----------+---+---+---+-----------+
^ ^
left right
```

**Iteration 4:**`sum = 4 + 6 = 10`

Found pair:

`(4, 6)`

Move both pointers inward.

```
+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---------------+---+---------------+
^
left
right
```

**Stopping Condition:**- The pointers now meet or cross (
`left >= right`

), and we stop the iteration.

- The pointers now meet or cross (

**Final Output**

```
Pairs in the array that sum to 10 are:
(1, 9)
(2, 8)
(3, 7)
(4, 6)
```

**9. Merge Two Sorted Arrays**

This function merges two sorted arrays into a single sorted array.

```
#include <stdio.h>
// Function to merge two sorted arrays
void mergeArrays(int arr1[], int size1, int arr2[], int size2, int arr3[]) {
int i = 0, j = 0, k = 0;
// Traverse both arrays and insert smaller value from arr1 or arr2 into arr3
while (i < size1 && j < size2) {
if (arr1[i] < arr2[j]) {
arr3[k++] = arr1[i++];
} else {
arr3[k++] = arr2[j++];
}
}
// Store remaining elements of first array
while (i < size1) {
arr3[k++] = arr1[i++];
}
// Store remaining elements of second array
while (j < size2) {
arr3[k++] = arr2[j++];
}
}
int main() {
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 4, 6, 8};
int size1 = sizeof(arr1) / sizeof(arr1[0]);
int size2 = sizeof(arr2) / sizeof(arr2[0]);
int arr3[size1 + size2]; // Resultant array
mergeArrays(arr1, size1, arr2, size2, arr3);
printf("Merged array: ");
for (int i = 0; i < size1 + size2; i++) {
printf("%d ", arr3[i]);
}
printf("\n");
return 0;
}
```

**Explanation with example:**

#### 1. **Initial Arrays**

We start with two pre-sorted arrays:

```
Array 1 (arr1): +---+---+---+---+
| 1 | 3 | 5 | 7 |
+---+---+---+---+
Array 2 (arr2): +---+---+---+---+
| 2 | 4 | 6 | 8 |
+---+---+---+---+
```

#### 2. **Merging Process**

We'll merge these arrays into a third array (`arr3`

), ensuring that the elements remain sorted.

**Initial Setup:**

```
Merged Array (arr3): (empty initially)
```

**Merging Iterations:**

**Iteration 1:**Compare the first elements of

`arr1`

and`arr2`

:`1`

(from`arr1`

) and`2`

(from`arr2`

).Since

`1 < 2`

, place`1`

in`arr3`

.

```
Merged Array (arr3): +---+
| 1 |
+---+
```

**Iteration 2:**Next elements to compare:

`3`

(from`arr1`

) and`2`

(from`arr2`

).Since

`2 < 3`

, place`2`

in`arr3`

.

```
Merged Array (arr3): +---+---+
| 1 | 2 |
+---+---+
```

**Iteration 3:**Next elements:

`3`

(from`arr1`

) and`4`

(from`arr2`

).Since

`3 < 4`

, place`3`

in`arr3`

.

```
Merged Array (arr3): +---+---+---+
| 1 | 2 | 3 |
+---+---+---+
```

**Iteration 4:**Next elements:

`5`

(from`arr1`

) and`4`

(from`arr2`

).Since

`4 < 5`

, place`4`

in`arr3`

.

```
Merged Array (arr3): +---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+
```

**Iteration 5:**Next elements:

`5`

(from`arr1`

) and`6`

(from`arr2`

).Since

`5 < 6`

, place`5`

in`arr3`

.

```
Merged Array (arr3): +---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+
```

**Iteration 6:**Next elements:

`7`

(from`arr1`

) and`6`

(from`arr2`

).Since

`6 < 7`

, place`6`

in`arr3`

.

```
Merged Array (arr3): +---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+
```

**Iteration 7:**Next elements:

`7`

(from`arr1`

) and`8`

(from`arr2`

).Since

`7 < 8`

, place`7`

in`arr3`

.

```
Merged Array (arr3): +---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+
```

**Iteration 8:**`arr1`

is exhausted, only`8`

remains in`arr2`

.Place

`8`

in`arr3`

.

```
Merged Array (arr3): +---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---
+---+---+---+---+---+---+
```

#### 3. Resultant Merged Array

The final merged array is:

```
Merged Array (arr3): +---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+
```

**10. Find the "Kth" Max and Min Element of an Array**

This function finds both the Kth maximum and minimum element in an unsorted array.

```
#include <stdio.h>
#include <limits.h>
// Function to insert into the max heap
void insertMaxHeap(int element, int heap[], int k) {
if (heap[k-1] < element) { // If new element is greater than the smallest in the max heap
heap[k-1] = element; // Replace the smallest
// Reorder the heap
for (int i = k-1; i > 0 && heap[i] > heap[(i-1)/2]; i = (i-1)/2) {
int temp = heap[i];
heap[i] = heap[(i-1)/2];
heap[(i-1)/2] = temp;
}
}
}
// Function to insert into the min heap
void insertMinHeap(int element, int heap[], int k) {
if (heap[k-1] > element) { // If new element is smaller than the largest in the min heap
heap[k-1] = element; // Replace the largest
// Reorder the heap
for (int i = k-1; i > 0 && heap[i] < heap[(i-1)/2]; i = (i-1)/2) {
int temp = heap[i];
heap[i] = heap[(i-1)/2];
heap[(i-1)/2] = temp;
}
}
}
// Function to find the Kth smallest and Kth largest element
void findKthElements(int arr[], int size, int k) {
int minHeap[k], maxHeap[k]; // Arrays to store the k elements
// Initialize heaps
for (int i = 0; i < k; i++) {
minHeap[i] = INT_MAX; // Fill min heap with maximum possible values
maxHeap[i] = INT_MIN; // Fill max heap with minimum possible values
}
// Process each element in the array
for (int i = 0; i < size; i++) {
insertMinHeap(arr[i], minHeap, k);
insertMaxHeap(arr[i], maxHeap, k);
}
// The root of maxHeap and minHeap are the Kth smallest and largest respectively
printf("Kth Min element is %d\n", minHeap[0]);
printf("Kth Max element is %d\n", maxHeap[0]);
}
int main() {
int numbers[] = {12, 3, 5, 7, 19, 2, 11, 17, 6, 10};
int size = sizeof(numbers) / sizeof(numbers[0]);
int k = 4; // Find the 4th smallest and largest elements
findKthElements(numbers, size, k);
return 0;
}
```

**11. Move All Zeroes to the End**

This function will move all zeroes in the array to the end while maintaining the relative order of other elements.

```
#include <stdio.h>
// Function to move all zeroes to the end of the array
void moveZeroesToEnd(int arr[], int size) {
int index = 0; // This will keep track of the position to insert non-zero elements
// Traverse the array
for (int i = 0; i < size; i++) {
if (arr[i] != 0) { // If the current element is not zero
arr[index++] = arr[i]; // Place it at the 'index' position and increment 'index'
}
}
// After all non-zero elements are moved, fill the rest of the array with zeroes
while (index < size) {
arr[index++] = 0; // Fill zeroes in the remaining positions
}
}
int main() {
int numbers[] = {0, 1, 0, 3, 12};
int size = sizeof(numbers) / sizeof(numbers[0]);
moveZeroesToEnd(numbers, size);
printf("Array after moving zeroes to end: ");
for (int i = 0; i < size; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
return 0;
}
```

**Explanation with example:**

#### 1. **Initial Array**

The initial array before any operations:

```
+---+---+---+---+---+
| 0 | 1 | 0 | 3 | 12|
+---+---+---+---+---+
```

#### 2. **Moving Non-Zero Elements**

A variable `index`

is initialized at `0`

. This variable tracks where the next non-zero element should be placed in the array.

**Iterative Process:**

**Iteration 1:**Element at

`i=0`

is`0`

.`index`

remains`0`

since the element is zero.

**Iteration 2:**Element at

`i=1`

is`1`

(non-zero).Place

`1`

at`arr[index]`

, then increment`index`

.

```
+---+---+---+---+---+
| 1 | 1 | 0 | 3 | 12|
+---+---+---+---+---+
^
index
```

**Iteration 3:**Element at

`i=2`

is`0`

.`index`

remains`1`

since the element is zero.

**Iteration 4:**Element at

`i=3`

is`3`

(non-zero).Place

`3`

at`arr[index]`

, then increment`index`

.

```
+---+---+---+---+---+
| 1 | 3 | 0 | 3 | 12|
+---+---+---+---+---+
^
index
```

**Iteration 5:**Element at

`i=4`

is`12`

(non-zero).Place

`12`

at`arr[index]`

, then increment`index`

.

```
+---+---+---+---+---+
| 1 | 3 | 12| 3 | 12|
+---+---+---+---+---+
^
index
```

#### 3. **Filling Remaining Positions with Zeros**

After moving all non-zero elements, `index`

is now at `3`

. The rest of the array should be filled with zeros.

- Fill zeros from
`index`

to`size-1`

.

```
+---+---+---+---+---+
| 1 | 3 | 12| 0 | 0 |
+---+---+---+---+---+
```

#### 4. **Final Array**

The final state of the array after executing the function is:

```
+---+---+---+---+---+
| 1 | 3 | 12| 0 | 0 |
+---+---+---+---+---+
```

**12. Circular Queue Implementation**

This section provides a basic implementation of a circular queue with enqueue, dequeue, and display functions.

```
#include <stdio.h>
#define SIZE 5
// Structure definition for circular queue
struct CircularQueue {
int items[SIZE];
int front, rear;
};
// Function to initialize the queue
void initQueue(struct CircularQueue *q) {
q->front = -1;
q->rear = -1;
}
// Function to check if the queue is full
int isFull(struct CircularQueue *q) {
if ((q->front == q->rear + 1) || (q->front == 0 && q->rear == SIZE - 1)) return 1;
return 0;
}
// Function to check if the queue is empty
int isEmpty(struct CircularQueue *q) {
if (q->front == -1) return 1;
return 0;
}
// Function to add an element to the queue
void enqueue(struct CircularQueue *q, int value) {
if (isFull(q))
printf("\nQueue is full!");
else {
if (q->front == -1) q->front = 0;
q->rear = (q->rear + 1) % SIZE;
q->items[q->rear] = value;
printf("\nInserted -> %d", value);
}
}
// Function to remove an element from the queue
int dequeue(struct CircularQueue *q) {
int element;
if (isEmpty(q)) {
printf("\nQueue is empty!");
return (-1);
} else {
element = q->items[q->front];
if (q->front == q->rear) {
q->front = -1;
q->rear = -1;
} // Queue has only one element, so we reset the queue after dequeuing it.
else {
q->front = (q->front + 1) % SIZE;
}
printf("\nDeleted element -> %d", element);
return (element);
}
}
// Function to display the elements of the queue
void display(struct CircularQueue *q) {
int i;
if (isEmpty(q))
printf(" \nEmpty Queue\n");
else {
printf("\nFront -> %d ", q->front);
printf("\nItems -> ");
for (i = q->front; i != q->rear; i = (i + 1) % SIZE) {
printf("%d ", q->items[i]);
}
printf("%d ", q->items[i]);
printf("\nRear -> %d \n", q->rear);
}
}
int main() {
struct CircularQueue q;
initQueue(&q);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
enqueue(&q, 4);
enqueue(&q, 5);
display(&q);
dequeue(&q);
display(&q);
enqueue(&q, 6);
display(&q);
return 0;
}
```

**13. Length of the Longest Consecutive Subsequence**

This function finds the longest subsequence in the array where the elements are consecutive integers.

```
#include <stdio.h>
#include <stdlib.h>
// Comparator function for qsort
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
// Function to find the longest subsequence with consecutive elements
int longestConsecutive(int arr[], int size) {
if (size == 0) return 0; // If array is empty, return 0
qsort(arr, size, sizeof(int), compare); // Sort the array
int longestStreak = 1, currentStreak = 1;
for (int i = 1; i < size; i++) {
if (arr[i] != arr[i - 1]) { // Check for no duplicates
if (arr[i] == arr[i - 1] + 1) { // Check if elements are consecutive
currentStreak++; // Increase current streak
} else {
longestStreak = (longestStreak > currentStreak) ? longestStreak : currentStreak;
currentStreak = 1; // Reset current streak
}
}
}
return (longestStreak > currentStreak) ? longestStreak : currentStreak; // Return the maximum of longest and current streak
}
int main() {
int numbers[] = {1, 9, 3, 10, 4, 20, 2};
int size = sizeof(numbers) / sizeof(numbers[0]);
printf("Length of the longest consecutive elements sequence is %d\n", longestConsecutive(numbers, size));
return 0;
}
```

**Explanation with example:**

#### 1. **Initial Array**

The original, unsorted array is:

```
+---+---+---+----+---+----+---+
| 1 | 9 | 3 | 10 | 4 | 20 | 2 |
+---+---+---+----+---+----+---+
```

#### 2. **Sorting the Array**

First, the array is sorted using `qsort`

with the provided comparator function.

**Sorted Array:**

```
+---+---+---+---+---+----+----+
| 1 | 2 | 3 | 4 | 9 | 10 | 20 |
+---+---+---+---+---+----+----+
```

#### 3. **Finding the Longest Consecutive Subsequence**

Variables `longestStreak`

and `currentStreak`

are initialized to `1`

.

**Iterative Process:**

**Iteration 1:**Compare`2`

(second element) with`1`

(first element).- Since
`2 == 1 + 1`

, increment`currentStreak`

to`2`

.

- Since

```
Current streak: 2
Longest streak: 1
```

**Iteration 2:**Compare`3`

with`2`

.- Since
`3 == 2 + 1`

, increment`currentStreak`

to`3`

.

- Since

```
Current streak: 3
Longest streak: 1
```

**Iteration 3:**Compare`4`

with`3`

.- Since
`4 == 3 + 1`

, increment`currentStreak`

to`4`

.

- Since

```
Current streak: 4
Longest streak: 1
```

**Iteration 4:**Compare`9`

with`4`

.- Since
`9 != 4 + 1`

, update`longestStreak`

to`4`

(max of`longestStreak`

and`currentStreak`

) and reset`currentStreak`

to`1`

.

- Since

```
Current streak: 1
Longest streak: 4
```

**Iteration 5:**Compare`10`

with`9`

.- Since
`10 == 9 + 1`

, increment`currentStreak`

to`2`

.

- Since

```
Current streak: 2
Longest streak: 4
```

**Iteration 6:**Compare`20`

with`10`

.- Since
`20 != 10 + 1`

, update`longestStreak`

to`4`

and reset`currentStreak`

to`1`

.

- Since

```
Current streak: 1
Longest streak: 4
```

#### 4. **Final Computation**

After completing the loop, check if the current streak should update the longest streak one last time.

```
Final Longest Streak: 4
```

#### 5. **Output**

The final output for the example is:

```
Length of the longest consecutive elements sequence is 4
```

**14. Find the Contiguous Subarray with the Largest Product**

This function finds the contiguous subarray within an array (containing at least one number) which has the largest product.

```
#include <stdio.h>
// Function to find the maximum product of a contiguous subarray
int maxProduct(int arr[], int size) {
if (size == 0) return 0; // Handle empty array edge case
int maxProd = arr[0]; // Assume the max product is the first element
int minProd = arr[0]; // Also assume the min product is the first element for handling negative numbers
int result = arr[0]; // Initialize result as the first element
// Loop through the array starting from the second element
for (int i = 1; i < size; i++) {
if (arr[i] < 0) { // If the current element is negative, swap max and min
int temp = maxProd;
maxProd = minProd;
minProd = temp;
}
// Update the maxProd and minProd
maxProd = (arr[i] > maxProd * arr[i]) ? arr[i] : maxProd * arr[i];
minProd = (arr[i] < minProd * arr[i]) ? arr[i] : minProd * arr[i];
// Update the result if needed
result = (maxProd > result) ? maxProd : result;
}
return result; // Return the maximum product found
}
int main() {
int numbers[] = {2, 3, -2, 4};
int size = sizeof(numbers) / sizeof(numbers[0]);
printf("Maximum product of a contiguous subarray is %d\n", maxProduct(numbers, size));
return 0;
}
```

**Explanation with example:**

#### 1. **Initial Array**

The array given is:

```
+---+---+---+---+
| 2 | 3 | -2| 4 |
+---+---+---+---+
```

#### 2. **Initial Setup**

**maxProd**is initialized to the first element`2`

.**minProd**is also initialized to the first element`2`

.**result**is initialized to`2`

, the first element as well.

**Visual Setup:**

```
maxProd = 2, minProd = 2, result = 2
```

#### 3. **Iterative Process**

We start from the second element and proceed through the array:

**Iteration 1 (Element at index 1 is**`3`

):Since

`3`

is positive,`maxProd`

and`minProd`

are not swapped.Calculate

`maxProd = max(3, 2*3) = 6`

Calculate

`minProd = min(3, 2*3) = 3`

Update

`result = max(result, maxProd) = 6`

```
Current Values:
maxProd = 6, minProd = 3, result = 6
```

**Iteration 2 (Element at index 2 is**`-2`

):Since

`-2`

is negative, swap`maxProd`

and`minProd`

.Calculate

`maxProd = max(-2, 3*(-2)) = -2`

Calculate

`minProd = min(-2, 6*(-2)) = -12`

Update

`result = max(result, maxProd) = 6`

```
Current Values after swap and recalculation:
maxProd = -2, minProd = -12, result = 6
```

**Iteration 3 (Element at index 3 is**`4`

):Since

`4`

is positive,`maxProd`

and`minProd`

are not swapped.Calculate

`maxProd = max(4, -2*4) = 4`

Calculate

`minProd = min(4, -12*4) = -48`

Update

`result = max(result, maxProd) = 6`

```
Current Values:
maxProd = 4, minProd = -48, result = 6
```

#### 4. **Final Output**

The maximum product of a contiguous subarray is `6`

, which is the product of the subarray `{2, 3}`

.

**15. Spiral Order Matrix Traversal**

This function will traverse a matrix in spiral order and print the elements.

```
#include <stdio.h>
#define R 3
#define C 6
// Function to print the matrix in spiral order
void spiralPrint(int m, int n, int a[R][C]) {
int i, k = 0, l = 0;
/* k - starting row index
m - ending row index
l - starting column index
n - ending column index
i - iterator */
while (k < m && l < n) {
// Print the first row from the remaining rows
for (i = l; i < n; ++i) {
printf("%d ", a[k][i]);
}
k++;
// Print the last column from the remaining columns
for (i = k; i < m; ++i) {
printf("%d ", a[i][n-1]);
}
n--;
// Print the last row from the remaining rows
if (k < m) {
for (i = n-1; i >= l; --i) {
printf("%d ", a[m-1][i]);
}
m--;
}
// Print the first column from the remaining columns
if (l < n) {
for (i = m-1; i >= k; --i) {
printf("%d ", a[i][l]);
}
l++;
}
}
}
int main() {
int a[R][C] = {
{1, 2, 3, 4, 5, 6},
{7, 8, 9, 10, 11, 12},
{13, 14, 15, 16, 17, 18}
};
spiralPrint(R, C, a);
return 0;
}
```

**Explanation with example:**

**Initial Matrix Setup**

```
+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 |
| 7 | 8 | 9 |10 |11 |12 |
|13 |14 |15 |16 |17 |18 |
+---+---+---+---+---+---+
```

#### Step 1: Print the first row

Start by printing the first row from the remaining rows. Increment `k`

after printing to move to the next row.

Output:

`1 2 3 4 5 6`

Increment

`k`

to 1.

```
Matrix after Step 1:
+---+---+---+---+---+---+
| x | x | x | x | x | x | <- Printed and marked as traversed
| 7 | 8 | 9 |10 |11 |12 |
|13 |14 |15 |16 |17 |18 |
+---+---+---+---+---+---+
```

#### Step 2: Print the last column

Next, print the last column from the remaining columns. Decrement `n`

after printing.

Output:

`12 18`

Decrement

`n`

to 5.

```
Matrix after Step 2:
+---+---+---+---+---+---+
| x | x | x | x | x | x |
| 7 | 8 | 9 |10 |11 | x | <- Printed last column, marked as traversed
|13 |14 |15 |16 |17 | x |
+---+---+---+---+---+---+
```

#### Step 3: Print the last row

If `k < m`

, print the last row from the remaining rows in reverse order.

Output:

`17 16 15 14 13`

Decrement

`m`

to 2.

```
Matrix after Step 3:
+---+---+---+---+---+---+
| x | x | x | x | x | x |
| 7 | 8 | 9 |10 |11 | x |
| x | x | x | x | x | x | <- Printed and marked as traversed
+---+---+---+---+---+---+
```

#### Step 4: Print the first column

If `l < n`

, print the first column from the remaining columns in reverse order.

Output:

`7`

Increment

`l`

to 1.

```
Matrix after Step 4:
+---+---+---+---+---+---+
| x | x | x | x | x | x |
| x | 8 | 9 |10 |11 | x | <- Printed first column, marked as traversed
| x | x | x | x | x | x |
+---+---+---+---+---+---+
```

#### Step 5: Print the second row (remaining elements)

After adjusting `k`

, `l`

, `m`

, and `n`

, print the second row from left to right.

- Output:
`8 9 10 11`

```
Final printed matrix:
+---+---+---+---+---+---+
| x | x | x | x | x | x |
| x | x | x | x | x | x | <- Printed and marked as traversed
| x | x | x | x | x | x |
+---+---+---+---+---+---+
```

Combining all outputs, the spiral order is:

```
1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11
```

**16. Minimum Swaps to Group All Elements Less Than or Equal to**`k`

**Together**

This function calculates the minimum number of swaps needed to bring all the elements less than or equal to `k`

together in an array.

```
#include <stdio.h>
// Function to count how many elements are less than or equal to k
int countLessEqual(int arr[], int size, int k) {
int count = 0;
for (int i = 0; i < size; i++) {
if (arr[i] <= k) {
count++;
}
}
return count;
}
// Function to find the minimum swaps required to group all elements <= k together
int minSwaps(int arr[], int size, int k) {
// First count how many elements are <= k
int countLE = countLessEqual(arr, size, k);
int bad = 0;
// Count elements in the first 'countLE' elements of the array that are greater than k
for (int i = 0; i < countLE; i++) {
if (arr[i] > k) {
bad++;
}
}
int ans = bad; // This is the initial number of swaps needed
// Using a sliding window technique to find the minimum 'bad' in any window of size 'countLE'
for (int i = 0, j = countLE; j < size; ++i, ++j) {
if (arr[i] > k) bad--; // Decrease bad count of left element if it's > k
if (arr[j] > k) bad++; // Increase bad count of right element if it's > k
ans = (bad < ans) ? bad : ans; // Update the minimum swaps needed
}
return ans;
}
int main() {
int arr[] = {2, 7, 9, 5, 8, 7, 4};
int k = 5;
int size = sizeof(arr) / sizeof(arr[0]);
printf("Minimum swaps required: %d\n", minSwaps(arr, size, k));
return 0;
}
```

**Explanation with example:**

#### Initial Array Setup

```
+---+---+---+---+---+---+---+
| 2 | 7 | 9 | 5 | 8 | 7 | 4 |
+---+---+---+---+---+---+---+
```

Here, `k = 5`

.

#### Step 1: Count Elements <= k

First, count how many elements are less than or equal to `k`

. This is done by the function `countLessEqual`

.

Elements

`<= 5`

are`2, 5, 4`

.Count: 3 elements.

#### Step 2: Calculate Initial 'bad' Count

Calculate how many elements in the first `countLE = 3`

elements of the array are greater than `k`

.

First

`countLE`

elements:`2, 7, 9`

- Elements
`> 5`

are`7, 9`

.

- Elements
Initial

`bad`

count: 2 elements.

#### Step 3: Sliding Window Technique

Use a sliding window of size `countLE`

to find the minimum number of elements `> k`

in any contiguous subarray of size `countLE`

.

**Initial Setup:**

- Window:
`2, 7, 9`

->`bad = 2`

**Slide the window and update 'bad' count:**

- Shift window right by one element at a time and adjust the
`bad`

count by considering the new element at the right end of the window and removing the influence of the leftmost element of the previous window.

```
Initial window: 2, 7, 9 -> bad = 2
Slide 1: 7, 9, 5 -> bad remains 2 (7 and 9 are still > k)
Slide 2: 9, 5, 8 -> bad remains 2 (9 and 8 are > k)
Slide 3: 5, 8, 7 -> bad remains 2 (8 and 7 are > k)
Slide 4: 8, 7, 4 -> bad remains 2 (8 and 7 are > k)
```

Calculate and keep track of the minimum

`bad`

found during the sliding.- Minimum
`bad`

found: 2 (it never decreases below 2)

- Minimum

#### Step 4: Return the Result

Return the minimum `bad`

value, which represents the minimum number of swaps needed to group all elements `<= k`

together.

```
Minimum swaps required: 2
```

**17. Smallest Missing Positive Integer**

This function finds the smallest missing positive integer from an unsorted array.

```
#include <stdio.h>
// Utility function to swap two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to segregate positive numbers from others
int segregate(int arr[], int size) {
int j = 0;
for (int i = 0; i < size; i++) {
if (arr[i] <= 0) {
swap(&arr[i], &arr[j]);
j++;
}
}
return j;
}
// Function to find the smallest missing positive number
int findMissingPositive(int arr[], int size) {
for (int i = 0; i < size; i++) {
// Use elements as index and mark the corresponding positions
int pos = abs(arr[i]) - 1;
if (pos >= 0 && pos < size && arr[pos] > 0) {
arr[pos] = -arr[pos];
}
}
// The first index which has positive number is the smallest missing positive number
for (int i = 0; i < size; i++) {
if (arr[i] > 0) {
return i + 1;
}
}
return size + 1;
}
// Function to find the smallest missing positive integer
int findSmallestMissing(int arr[], int size) {
int shift = segregate(arr, size); // segregate positive numbers from non-positive
return findMissingPositive(arr + shift, size - shift); // find the smallest missing positive number
}
int main() {
int arr[] = {3, 4, -1, 1};
int size = sizeof(arr) / sizeof(arr[0]);
printf("The smallest missing positive integer is %d\n", findSmallestMissing(arr, size));
return 0;
}
```

**Explanation with example:**

#### Initial Array Setup

```
+---+---+----+---+
| 3 | 4 | -1 | 1 |
+---+---+----+---+
```

#### Step 1: Segregate Positive Numbers

The `segregate`

function rearranges the array so that all non-positive numbers are moved to the left side, and all positive numbers are on the right.

**Segregation Process:**

Initialize

`j = 0`

to act as the pointer for the swap position.Iterate over the array, and whenever a non-positive number is found, swap it with the element at index

`j`

, then increment`j`

.

```
i = 0, arr[0] = 3 (positive, no swap needed, continue)
i = 1, arr[1] = 4 (positive, no swap needed, continue)
i = 2, arr[2] = -1 (non-positive, swap with arr[0])
After swap: +----+---+---+---+
| -1 | 4 | 3 | 1 |
+----+---+---+---+
j increments to 1
i = 3, arr[3] = 1 (positive, no swap needed, continue)
```

After segregation, the array is `{-1, 4, 3, 1}`

, and `j`

(count of non-positive integers) is `1`

.

#### Step 2: Finding Missing Positive

The `findMissingPositive`

function is called on the subarray starting from index `j`

(`arr[j]`

to `arr[size-1]`

).

**Initial Subarray for Missing Positive Search:**

```
+---+---+---+
| 4 | 3 | 1 |
+---+---+---+
```

**Finding Process:**

- Iterate over the subarray. For each element, calculate the position as
`abs(arr[i]) - 1`

. If this position is within the bounds of the subarray and the element at this position is positive, negate it to mark it as found.

```
i = 0, pos = 4 - 1 = 3 (out of bounds, ignore)
i = 1, pos = 3 - 1 = 2
Mark found: +---+---+---+
| 4 | 3 | -1|
+---+---+---+
i = 2, pos = 1 - 1 = 0
Mark found: +---+---+---+
| -4 | 3 | -1|
+---+---+---+
```

- Look for the first index that has a positive value, which indicates the smallest missing positive integer.

```
Since index 1 (value 3) is the first positive,
the smallest missing positive integer is 1 + 1 = 2.
```

```
The smallest missing positive integer is 2.
```

**18. Water Trapping Problem**

This function calculates how much water can be trapped between bars given an elevation map, where each bar has a width of 1 unit.

```
#include <stdio.h>
// Function to calculate the maximum water that can be trapped
int trapWater(int heights[], int size) {
if (size < 3) return 0; // Less than 3 bars can't trap any water
int left[size]; // Array to store the maximum height from the left
int right[size]; // Array to store the maximum height from the right
int water = 0; // Total water trapped
left[0] = heights[0]; // The first element is the left max for itself
for (int i = 1; i < size; i++) {
left[i] = (heights[i] > left[i - 1]) ? heights[i] : left[i - 1];
}
right[size - 1] = heights[size - 1]; // The last element is the right max for itself
for (int i = size - 2; i >= 0; i--) {
right[i] = (heights[i] > right[i + 1]) ? heights[i] : right[i + 1];
}
for (int i = 0; i < size; i++) {
// Calculate the trapped water at current bar
water += (left[i] < right[i] ? left[i] : right[i]) - heights[i];
}
return water; // Return the total water trapped
}
int main() {
int heights[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
int size = sizeof(heights) / sizeof(heights[0]);
printf("Total water trapped: %d\n", trapWater(heights, size));
return 0;
}
```

**Explanation with example:**

#### Initial Array Setup

```
Bar heights:
+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 0 | 2 | 1 | 0 | 1 | 3 | 2 | 1 | 2 | 1 |
+---+---+---+---+---+---+---+---+---+---+---+---+
```

#### Step 1: Compute Maximum Heights from the Left

```
left[0] = 0 // Starting point, no bars to the left
left[1] = max(height[1], left[0]) = max(1, 0) = 1
left[2] = max(height[2], left[1]) = max(0, 1) = 1
left[3] = max(height[3], left[2]) = max(2, 1) = 2
... Continue this for each bar
Final left[] array:
+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 |
+---+---+---+---+---+---+---+---+---+---+---+---+
```

#### Step 2: Compute Maximum Heights from the Right

```
right[11] = 1 // Starting from the end, no bars to the right
right[10] = max(height[10], right[11]) = max(2, 1) = 2
right[9] = max(height[9], right[10]) = max(1, 2) = 2
right[8] = max(height[8], right[9]) = max(2, 2) = 2
... Continue this in reverse order
Final right[] array:
+---+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 1 |
+---+---+---+---+---+---+---+---+---+---+---+---+
```

#### Step 3: Calculate Trapped Water

For each bar, calculate the trapped water using the formula:

```
water[i] = (min(left[i], right[i]) - height[i])
```

```
Example for bar 2:
water[2] = (min(left[2], right[2]) - height[2]) = (min(1, 3) - 0) = 1
```

Calculate this for each bar and sum up the results:

```
+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 1 | 2 | 0 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+---+---+---+
Total water trapped = 5
```

```
Total water trapped: 5
```

**19. Subarray with Given Sum**

This function finds if there is a subarray with a sum equal to a given value.

```
#include <stdio.h>
// Function to find a subarray with a given sum
int subarraySum(int arr[], int size, int sum) {
int curr_sum = arr[0], start = 0;
// Add elements to curr_sum and if it exceeds the sum, start removing elements from start
for (int i = 1; i <= size; i++) {
// While the current sum exceeds the sum, subtract the starting elements
while (curr_sum > sum && start < i-1) {
curr_sum -= arr[start];
start++;
}
// If current sum becomes equal to sum, return true
if (curr_sum == sum) {
printf("Sum found between indexes %d and %d\n", start, i-1);
return 1;
}
// Add this element to curr_sum
if (i < size) {
curr_sum += arr[i];
}
}
printf("No subarray found\n");
return 0;
}
int main() {
int arr[] = {15, 2, 4, 8, 9, 5, 10, 23};
int size = sizeof(arr) / sizeof(arr[0]);
int sum = 23;
subarraySum(arr, size, sum);
return 0;
}
```

**Explanation with example:**

#### Initial Array Setup

```
Array:
+----+---+---+---+---+---+----+----+
| 15 | 2 | 4 | 8 | 9 | 5 | 10 | 23 |
+----+---+---+---+---+---+----+----+
```

The target sum to find is `23`

.

#### Step 1: Initialize Variables

`curr_sum`

starts as the first element,`15`

.`start`

is initialized at index`0`

.

#### Step 2: Iterate and Adjust Window

The function iterates through the array, expanding the window (summing more elements) until the `curr_sum`

exceeds the target `sum`

. When it exceeds, it shrinks the window from the start.

**Process Iteration with Details:**

**i = 1**:`curr_sum = 15`

- Add
`arr[1] = 2`

to`curr_sum`

. Now`curr_sum = 17`

.

- Add
**i = 2**:`curr_sum = 17`

- Add
`arr[2] = 4`

to`curr_sum`

. Now`curr_sum = 21`

.

- Add
**i = 3**:`curr_sum = 21`

Add

`arr[3] = 8`

to`curr_sum`

. Now`curr_sum = 29`

.`curr_sum > sum`

(29 > 23). Start shrinking the window:- Subtract
`arr[start] = 15`

from`curr_sum`

and increment`start`

. Now`curr_sum = 14`

,`start = 1`

.

- Subtract
Add

`arr[3] = 8`

again (as loop iterates). Now`curr_sum = 22`

.

**i = 4**:`curr_sum = 22`

Add

`arr[4] = 9`

to`curr_sum`

. Now`curr_sum = 31`

.`curr_sum > sum`

(31 > 23). Continue shrinking the window:Subtract

`arr[start] = 2`

from`curr_sum`

and increment`start`

. Now`curr_sum = 29`

,`start = 2`

.Subtract

`arr[start] = 4`

from`curr_sum`

and increment`start`

. Now`curr_sum = 25`

,`start = 3`

.Subtract

`arr[start] = 8`

from`curr_sum`

and increment`start`

. Now`curr_sum = 17`

,`start = 4`

.

Add

`arr[4] = 9`

again. Now`curr_sum = 26`

.

**i = 5**:`curr_sum = 26`

Add

`arr[5] = 5`

to`curr_sum`

. Now`curr_sum = 31`

.`curr_sum > sum`

. Shrink:- Subtract
`arr[start] = 9`

from`curr_sum`

and increment`start`

. Now`curr_sum = 22`

,`start = 5`

.

- Subtract
Add

`arr[5] = 5`

again. Now`curr_sum = 27`

.

**i = 6**:`curr_sum = 27`

Add

`arr[6] = 10`

to`curr_sum`

. Now`curr_sum = 37`

.`curr_sum > sum`

. Shrink:- Subtract
`arr[start] = 5`

from`curr_sum`

and increment`start`

. Now`curr_sum = 32`

,`start = 6`

.

- Subtract
Add

`arr[6] = 10`

again. Now`curr_sum = 42`

.`curr_sum > sum`

. Shrink:- Subtract
`arr[start] = 10`

from`curr_sum`

and increment`start`

. Now`curr_sum = 32`

,`start = 7`

.

- Subtract
Add

`arr[6] = 10`

again. Now`curr_sum = 33`

.

**i = 7**:`curr_sum = 33`

Add

`arr[7] = 23`

to`curr_sum`

. Now`curr_sum = 33`

.`

curr_sum > sum`. Shrink: - Subtract`

arr[start] = 10`from`

curr_sum`. Now`

curr_sum = 23`,`

start = 8`.

- The
`curr_sum`

now matches the target sum (`23`

).

#### Final Output

```
Sum found between indexes 7 and 7
```

**20. Longest Substring Without Repeating Characters**

This function finds the longest substring without repeating characters.

```
#include <stdio.h>
#include <string.h>
#define NO_OF_CHARS 256
// Function to find the longest substring without repeating characters
int longestUniqueSubstr(char *str) {
int n = strlen(str);
int res = 0; // Result
int last_index[NO_OF_CHARS]; // Last index of all characters (initialized to -1)
memset(last_index, -1, sizeof(last_index));
int i = 0;
for (int j = 0; j < n; j++) {
// Find the last index of str[j]
// Update i (start index of current window) as maximum of current value of i and last index plus 1
i = (last_index[str[j]] + 1 > i) ? last_index[str[j]] + 1 : i;
// Update result if we get a better length
res = (res > j - i + 1) ? res : j - i + 1;
// Update last index of j
last_index[str[j]] = j;
}
return res;
}
int main() {
char str[] = "abcabcbb";
printf("The length of the longest non-repeating character substring is %d\n", longestUniqueSubstr(str));
return 0;
}
```

**Explanation with example:**

#### Initial String Setup

```
String: "abcabcbb"
```

#### Detailed Process

**Initialize Arrays and Variables:**`n`

is the length of the string.`res`

to keep track of the length of the longest substring found.`last_index`

array of size 256 (for all ASCII characters), initialized to`-1`

.

```
n = 8
res = 0
last_index[256] = {-1, -1, -1, ...}
```

**Iterate Through the String:**- Use two indices,
`i`

and`j`

.`i`

maintains the start of the substring without repetitions, and`j`

iterates through the string.

- Use two indices,

#### Iteration Explained with the String "abcabcbb":

**For each character**`j`

from 0 to 7:**j = 0**(character 'a'):`last_index['a'] = -1`

,`i`

remains 0.Update

`res`

to 1 (`j - i + 1 = 0 - 0 + 1`

).Update

`last_index['a'] = 0`

.

```
Window: "a"
last_index['a'] = 0, res = 1
```

**j = 1**(character 'b'):`last_index['b'] = -1`

,`i`

remains 0.Update

`res`

to 2.Update

`last_index['b'] = 1`

.

```
Window: "ab"
last_index['b'] = 1, res = 2
```

**j = 2**(character 'c'):`last_index['c'] = -1`

,`i`

remains 0.Update

`res`

to 3.Update

`last_index['c'] = 2`

.

```
Window: "abc"
last_index['c'] = 2, res = 3
```

**j = 3**(character 'a'):`last_index['a'] = 0`

,`i`

becomes 1 (`last_index['a'] + 1`

).Update

`res`

to 3.Update

`last_index['a'] = 3`

.

```
Window shifts to "bca"
last_index['a'] = 3, res = 3
```

**Continue this logic through the string...**

**Final Calculation:**- The maximum value of
`res`

during this process is the length of the longest non-repeating character substring. For "abcabcbb", it's`3`

, corresponding to the substring "abc".

- The maximum value of

```
The length of the longest non-repeating character substring is 3
```