Skip to main content
HashnodeJyotiprakash's Blog

Command Palette

Search for a command to run...

DSA: Arrays

Updated
•51 min read
J
Jyotiprakash Mishra

I am Jyotiprakash, a deeply driven computer systems engineer, software developer, teacher, and philosopher. With a decade of professional experience, I have contributed to various cutting-edge software products in network security, mobile apps, and healthcare software at renowned companies like Oracle, Yahoo, and Epic. My academic journey has taken me to prestigious institutions such as the University of Wisconsin-Madison and BITS Pilani in India, where I consistently ranked among the top of my class.

At my core, I am a computer enthusiast with a profound interest in understanding the intricacies of computer programming. My skills are not limited to application programming in Java; I have also delved deeply into computer hardware, learning about various architectures, low-level assembly programming, Linux kernel implementation, and writing device drivers. The contributions of Linus Torvalds, Ken Thompson, and Dennis Ritchie—who revolutionized the computer industry—inspire me. I believe that real contributions to computer science are made by mastering all levels of abstraction and understanding systems inside out.

In addition to my professional pursuits, I am passionate about teaching and sharing knowledge. I have spent two years as a teaching assistant at UW Madison, where I taught complex concepts in operating systems, computer graphics, and data structures to both graduate and undergraduate students. Currently, I am an assistant professor at KIIT, Bhubaneswar, where I continue to teach computer science to undergraduate and graduate students. I am also working on writing a few free books on systems programming, as I believe in freely sharing knowledge to empower others.

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:

  1. Accessing:

    • Directly access any element with its index.

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

  2. 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.

  3. 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.

  4. 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.

  5. Updating:

    • Modify the value of an element at a specific index.

    • Time complexity: O(1).

  6. 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).

  7. Iterating:

    • Go through each element, typically for processing or condition checking.

    • Time complexity: O(n).

  8. 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.

  9. 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.

  10. 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

  1. Find the Largest Element in an Array

    • Write a program to find the largest number in a given array.

  2. Check if the Array Contains a Given Element

    • Implement a function that checks whether an array contains a specific value.

  3. Calculate the Sum of Array Elements

    • Write a function to sum all the numbers in an array.

  4. Reverse an Array

    • Develop a method to reverse an array in place without using additional storage.

  5. 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

  1. Remove Duplicates from a Sorted Array

    • Modify the array so that it contains no duplicates, potentially reducing its size.

  2. Rotate Array to the Right

    • Implement a function that rotates the elements of an array to the right by a given number of steps.

  3. 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.

  4. Merge Two Sorted Arrays

    • Merge two sorted arrays into one sorted array.

  5. 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

  1. 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.

  2. Implement a Circular Queue Using an Array

    • Create a circular queue with basic operations like enqueue, dequeue, and display.

  3. Find the Longest Consecutive Subsequence

    • Identify the length of the longest subsequence such that elements in the subsequence are consecutive integers.

  4. Maximum Product Subarray

    • Find the contiguous subarray within an array (containing at least one number) which has the largest product.

  5. Spiral Order Matrix Traversal

    • Given a 2D array, print it in spiral order.

Expert Level

  1. 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.

  2. First Missing Positive

    • Given an unsorted integer array, find the smallest missing positive integer.

  3. 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.

  4. Subarray with Given Sum

    • Find a subarray that sums to a given number in an array of non-negative numbers.

  5. 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. 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.

  12. 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.

  13. 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.

  14. 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.

  15. 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.

  16. 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.

  17. 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.

  18. 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.

  19. 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.

  20. 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:

  1. i = 1:arr[1] is 1. No change since it's a duplicate.

  2. i = 2:arr[2] is 2. It's different from arr[j] (which is 1).

    • Increment j to 1.

    • Update arr[1] to 2.

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

  4. i = 4:arr[4] is 3. Different from arr[j] (which is 2).

    • Increment j to 2.

    • Update arr[2] to 3.

  5. i = 5:arr[5] is 4. Different from arr[j] (which is 3).

    • Increment j to 3.

    • Update arr[3] to 4.

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

  7. i = 7:arr[7] is 5. Different from arr[j] (which is 4).

    • Increment j to 4.

    • Update arr[4] to 5.

  8. 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:

  1. Swap 1 and 7

  2. Swap 2 and 6

  3. 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.

  1. 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:

  1. Swap 4 and 1

  2. 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.

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.
Current streak: 2
Longest streak: 1

  • Iteration 2: Compare 3 with 2.

    • Since 3 == 2 + 1, increment currentStreak to 3.
Current streak: 3
Longest streak: 1

  • Iteration 3: Compare 4 with 3.

    • Since 4 == 3 + 1, increment currentStreak to 4.
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.
Current streak: 1
Longest streak: 4

  • Iteration 5: Compare 10 with 9.

    • Since 10 == 9 + 1, increment currentStreak to 2.
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.
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 is3):

    • 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 is4):

    • 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 tokTogether

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.

  • 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)

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.

  • i = 2: curr_sum = 17

    • Add arr[2] = 4 to curr_sum. Now curr_sum = 21.

  • 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.

    • 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.

    • 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.

    • 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.

    • 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] = 10fromcurr_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

  1. 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, ...}

  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.

Iteration Explained with the String "abcabcbb":

  • For each characterj 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...

  1. 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 length of the longest non-repeating character substring is 3
#dsa#data-structures#data-structure-and-algorithms#algorithms#arrays

Comments

Join the discussion

No comments yet. Be the first to comment.

More from this blog

Jyotiprakash's Blog

251 posts

I'm Jyotiprakash, a software dev and professor at KIIT, with expertise in system programming.