Introduction to Arrays

An array is a data structure that stores a collection of elements, typically of the same data type, in a contiguous block of memory. Arrays are indexed, which means each element can be accessed by its position in the array, starting from zero.

Characteristics:

Fixed Size: The size of an array is defined at the time of its declaration and cannot be changed.
Homogeneous Elements: All elements in an array are of the same data type.
Contiguous Memory Allocation: Elements are stored in continuous memory locations.
Indexed Access: Each element can be accessed using its index.

Types of Arrays

Single-Dimensional Arrays

A single-dimensional array, also known as a one-dimensional array, is a list of elements stored in a single row.

Example in C:

int numbers[5] = {1, 2, 3, 4, 5};

Multi-Dimensional Arrays

Multi-dimensional arrays consist of more than one row or column. The most common multi-dimensional array is the two-dimensional array.

Example in C:

int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

Advantages:

Fast Access: Elements can be accessed quickly using their index.
Ease of Iteration: Arrays can be easily iterated using loops.
Memory Efficiency: Arrays have minimal overhead compared to other data structures.

Disadvantages:

Fixed Size: The size of the array cannot be changed once defined.
Wasted Memory: If the array size is overestimated, memory may be wasted.
Costly Insertion/Deletion: Inserting or deleting elements can be costly as it may require shifting elements.

Explanation of Row Major Order

Row major order is a method for storing multi-dimensional arrays in linear memory. In this arrangement, the elements of each row of a multi-dimensional array are stored in contiguous memory locations. This means that the complete row is stored before the next row begins.

For example, consider a 2-D array:

int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

In row major order, the elements will be stored in memory as:

1, 2, 3, 4, 5, 6, 7, 8, 9

Address Calculation Formula for 1-D and 2-D Arrays

1-D Array

For a 1-D array, the address of an element can be calculated using the formula:

Address of A[i] = Base_Address + (i * Size_of_Element)

Where:

Base_Address is the address of the first element of the array.
i is the index of the element.
Size_of_Element is the size of each element in the array (e.g., 4 bytes for an int).

2-D Array

For a 2-D array stored in row major order, the address of an element can be calculated using the formula:

Address of A[i][j] = Base_Address + [(i * Number_of_Columns) + j] * Size_of_Element

Where:

Base_Address is the address of the first element of the array.
i is the row index.
j is the column index.
Number_of_Columns is the total number of columns in the 2-D array.
Size_of_Element is the size of each element in the array.

1-D Array Example

Consider a 1-D array int arr[5] = {10, 20, 30, 40, 50}; with Base_Address = 1000 and Size_of_Element = 4 bytes.

To find the address of arr[3]:

Address of arr[3] = 1000 + (3 * 4) = 1000 + 12 = 1012

2-D Array Example

Consider a 2-D array int matrix[3][3] with Base_Address = 2000 and Size_of_Element = 4 bytes.

To find the address of matrix[2][1]:

Address of matrix[2][1] = 2000 + [(2 * 3) + 1] * 4
                        = 2000 + [6 + 1] * 4
                        = 2000 + 7 * 4
                        = 2000 + 28
                        = 2028

Dynamic Memory Allocation (DMA) – 1-D and 2-D Arrays

Dynamic memory allocation allows programs to allocate memory during runtime. This is particularly useful when the size of the data structure (such as an array) is not known at compile time. The allocated memory can be resized or freed as needed, enabling efficient use of memory.

Allocating Memory for 1-D Arrays Dynamically

To allocate memory for a 1-D array dynamically, you can use the malloc() or calloc() functions in C.

malloc() allocates a specified number of bytes and returns a pointer to the first byte of the allocated memory.

int *arr;
int n = 5;
arr = (int *)malloc(n * sizeof(int));

Allocating Memory for 2-D Arrays Dynamically

To allocate memory for a 2-D array dynamically, you typically use an array of pointers.

int **matrix;
int rows = 3, cols = 3;
matrix = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
    matrix[i] = (int *)malloc(cols * sizeof(int));
}

Allocating Memory for 2-D Jagged Arrays Dynamically

A jagged array, also known as an array of arrays, is a 2-D array where the rows can have different lengths.

int **jaggedArray;
int rows = 3;
jaggedArray = (int **)malloc(rows * sizeof(int *));
jaggedArray[0] = (int *)malloc(2 * sizeof(int)); // 1st row with 2 elements
jaggedArray[1] = (int *)malloc(3 * sizeof(int)); // 2nd row with 3 elements
jaggedArray[2] = (int *)malloc(4 * sizeof(int)); // 3rd row with 4 elements

To avoid memory leaks, it is crucial to deallocate memory that was allocated dynamically using the free() function.

Deallocating 1-D Array

free(arr);

Deallocating 2-D Array

for (int i = 0; i < rows; i++) {
    free(matrix[i]);
}
free(matrix);

Deallocating 2-D Jagged Array

for (int i = 0; i < rows; i++) {
    free(jaggedArray[i]);
}
free(jaggedArray);

Pointers to Array, Pointer to Structure, Array of Pointers

Pointers are variables that store the memory address of another variable. They are powerful tools in programming because they allow for direct memory access and manipulation, which can lead to more efficient and flexible code. Pointers are essential for dynamic memory allocation, handling arrays, and structures.

Pointers to Arrays and Their Usage

A pointer to an array holds the address of the first element of the array. It can be used to iterate over the array elements or to pass arrays to functions efficiently.

int arr[5] = {1, 2, 3, 4, 5};
int *ptr = arr; // ptr points to the first element of arr

for (int i = 0; i < 5; i++) {
    printf("%d ", *(ptr + i)); // Access array elements using the pointer
}

Pointer to Structure and Accessing Structure Members Using Pointers

A pointer to a structure stores the address of a structure variable. You can access the structure members using the arrow operator (->).

struct Point {
    int x;
    int y;
};

struct Point p1 = {10, 20};
struct Point *ptr = &p1;

printf("x = %d, y = %d\n", ptr->x, ptr->y); // Access members using the pointer

Arrays of Pointers and Their Applications

An array of pointers is a collection of pointers, each pointing to a different variable or memory block. This is useful for creating arrays of strings, arrays of dynamic arrays, or managing multiple dynamic memory allocations.

Example: Array of Strings

char *arr[] = {"Hello", "World", "Pointers", "in", "C"};
int n = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < n; i++) {
    printf("%s ", arr[i]); // Print each string using the array of pointers
}

Example: Array of Dynamic Arrays

int *arr[3];
int sizes[] = {2, 3, 4};

// Allocating memory for each row
for (int i = 0; i < 3; i++) {
    arr[i] = (int *)malloc(sizes[i] * sizeof(int));
}

// Initializing and printing values
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < sizes[i]; j++) {
        arr[i][j] = i + j;
        printf("%d ", arr[i][j]);
    }
    printf("\n");
}

// Freeing allocated memory
for (int i = 0; i < 3; i++) {
    free(arr[i]);
}

Pointer to Array Example

int arr[3] = {10, 20, 30};
int (*ptr)[3] = &arr; // Pointer to the entire array

for (int i = 0; i < 3; i++) {
    printf("%d ", (*ptr)[i]); // Access elements using pointer to array
}

Pointer to Structure Example

struct Student {
    int id;
    char name[20];
};

struct Student s1 = {1, "John Doe"};
struct Student *ptr = &s1;

printf("ID: %d, Name: %s\n", ptr->id, ptr->name); // Access members using pointer

Array of Pointers Example

int a = 10, b = 20, c = 30;
int *arr[3] = {&a, &b, &c}; // Array of pointers to integers

for (int i = 0; i < 3; i++) {
    printf("%d ", *arr[i]); // Print values using array of pointers
}

Array Abstract Data Type (ADT)

An Abstract Data Type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. An ADT encapsulates the underlying data structure, providing an interface to the user while hiding the implementation details.

Importance of ADTs:

Encapsulation: Hides the implementation details and exposes only necessary operations.
Modularity: Promotes modular design, making code easier to manage and maintain.
Reusability: ADTs can be reused across different programs and projects.
Interchangeability: Allows changing the underlying data structure without altering the external interface.

An array ADT encapsulates an array and provides a set of operations that can be performed on the array. Here is how you can implement an array as an ADT in C.

Structure Definition

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;      // Pointer to the array elements
    int size;       // Current number of elements
    int capacity;   // Maximum capacity of the array
} ArrayADT;

Initialize Array ADT

ArrayADT* createArray(int capacity) {
    ArrayADT *arr = (ArrayADT *)malloc(sizeof(ArrayADT));
    arr->data = (int *)malloc(capacity * sizeof(int));
    arr->size = 0;
    arr->capacity = capacity;
    return arr;
}

Operations on Array ADT

Insertion

void insert(ArrayADT *arr, int element) {
    if (arr->size == arr->capacity) {
        printf("Array is full\n");
        return;
    }
    arr->data[arr->size] = element;
    arr->size++;
}

Deletion

void delete(ArrayADT *arr, int index) {
    if (index < 0 || index >= arr->size) {
        printf("Invalid index\n");
        return;
    }
    for (int i = index; i < arr->size - 1; i++) {
        arr->data[i] = arr->data[i + 1];
    }
    arr->size--;
}

Traversal

void traverse(ArrayADT *arr) {
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");
}

Search

int search(ArrayADT *arr, int element) {
    for (int i = 0; i < arr->size; i++) {
        if (arr->data[i] == element) {
            return i; // Element found, return its index
        }
    }
    return -1; // Element not found
}

Implementing an Enhanced Array ADT

Implement an Array Abstract Data Type (ADT) in a programming language of your choice that supports the following operations:

Creation: Initialize the array with a given capacity.
Insertion:
- Insert an element at the end of the array.
- Insert an element at a specified position (middle of the array).
Deletion:
- Delete an element from the end of the array.
- Delete an element from a specified position (middle of the array).
Search: Find the index of a specified element.
Data Retrieval:
- Retrieve a single value at a specified index.
- Retrieve a sub-array from a specified start index to an end index (not inclusive).
Free Memory: Deallocate the memory used by the array.
Increase Capacity: Automatically increase the capacity of the array if it becomes full.

ADT Structure

typedef struct {
    int *data;      // Pointer to the array elements
    int size;       // Current number of elements
    int capacity;   // Maximum capacity of the array
} ArrayADT;

Function Signatures

Create Array
```
 ArrayADT* createArray(int capacity);
```

Insert at End

 void insertAtEnd(ArrayADT *arr, int element);

Insert at Position

 void insertAtPosition(ArrayADT *arr, int element, int position);

Delete from End
```
 void deleteFromEnd(ArrayADT *arr);
```

Delete from Position

 void deleteFromPosition(ArrayADT *arr, int position);

Search

 int search(ArrayADT *arr, int element);

Retrieve Single Value

 int retrieveValue(ArrayADT *arr, int index);

Retrieve Sub-Array

 ArrayADT* retrieveSubArray(ArrayADT *arr, int from, int to);

Free Memory
```
 void freeArray(ArrayADT *arr);
```
Increase Capacity
```
void increaseCapacity(ArrayADT *arr);
```

Pseudo Code for Each Function

Create Array

 function createArray(capacity):
     arr = allocate memory for ArrayADT
     arr.data = allocate memory for capacity elements
     arr.size = 0
     arr.capacity = capacity
     return arr

Insert at End

 function insertAtEnd(arr, element):
     if arr.size == arr.capacity:
         increaseCapacity(arr)
     arr.data[arr.size] = element
     arr.size = arr.size + 1

Insert at Position

 function insertAtPosition(arr, element, position):
     if arr.size == arr.capacity:
         increaseCapacity(arr)
     if position < 0 or position > arr.size:
         print "Invalid position"
         return
     for i = arr.size to position step -1:
         arr.data[i] = arr.data[i - 1]
     arr.data[position] = element
     arr.size = arr.size + 1

Delete from End

 function deleteFromEnd(arr):
     if arr.size == 0:
         print "Array is empty"
         return
     arr.size = arr.size - 1

Delete from Position

 function deleteFromPosition(arr, position):
     if position < 0 or position >= arr.size:
         print "Invalid position"
         return
     for i = position to arr.size - 2:
         arr.data[i] = arr.data[i + 1]
     arr.size = arr.size - 1

Search

 function search(arr, element):
     for i = 0 to arr.size - 1:
         if arr.data[i] == element:
             return i
     return -1

Retrieve Single Value

 function retrieveValue(arr, index):
     if index < 0 or index >= arr.size:
         print "Invalid index"
         return -1
     return arr.data[index]

Retrieve Sub-Array

 function retrieveSubArray(arr, from, to):
     if from < 0 or to > arr.size or from >= to:
         print "Invalid indices"
         return null
     subArray = createArray(to - from)
     for i = from to to - 1:
         insertAtEnd(subArray, arr.data[i])
     return subArray

Free Memory

 function freeArray(arr):
     free(arr.data)
     free(arr)

Increase Capacity

function increaseCapacity(arr):
    newCapacity = arr.capacity * 2
    newData = allocate memory for newCapacity elements
    for i = 0 to arr.size - 1:
        newData[i] = arr.data[i]
    free(arr.data)
    arr.data = newData
    arr.capacity = newCapacity

Instructions

Implement the ArrayADT structure and each function in your chosen programming language.
Ensure that your program handles edge cases, such as inserting or deleting from an empty array or inserting/deleting at invalid positions.
Test your implementation with various inputs to verify correctness and robustness.

Implementation in C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;      // Pointer to the array elements
    int size;       // Current number of elements
    int capacity;   // Maximum capacity of the array
} ArrayADT;

// Function to create an array with a given capacity
ArrayADT* createArray(int capacity) {
    ArrayADT *arr = (ArrayADT *)malloc(sizeof(ArrayADT));
    arr->data = (int *)malloc(capacity * sizeof(int));
    arr->size = 0;
    arr->capacity = capacity;
    return arr;
}

// Function to increase the capacity of the array
void increaseCapacity(ArrayADT *arr) {
    int newCapacity = arr->capacity * 2;
    int *newData = (int *)malloc(newCapacity * sizeof(int));
    for (int i = 0; i < arr->size; i++) {
        newData[i] = arr->data[i];
    }
    free(arr->data);
    arr->data = newData;
    arr->capacity = newCapacity;
    printf("Array capacity increased to %d\n", newCapacity);
}

// Function to insert an element at the end of the array
void insertAtEnd(ArrayADT *arr, int element) {
    if (arr->size == arr->capacity) {
        increaseCapacity(arr);
    }
    arr->data[arr->size] = element;
    arr->size++;
}

// Function to insert an element at a specified position in the array
void insertAtPosition(ArrayADT *arr, int element, int position) {
    if (position < 0 || position > arr->size) {
        printf("Invalid position\n");
        return;
    }
    if (arr->size == arr->capacity) {
        increaseCapacity(arr);
    }
    for (int i = arr->size; i > position; i--) {
        arr->data[i] = arr->data[i - 1];
    }
    arr->data[position] = element;
    arr->size++;
}

// Function to delete an element from the end of the array
void deleteFromEnd(ArrayADT *arr) {
    if (arr->size == 0) {
        printf("Array is empty\n");
        return;
    }
    arr->size--;
}

// Function to delete an element from a specified position in the array
void deleteFromPosition(ArrayADT *arr, int position) {
    if (position < 0 || position >= arr->size) {
        printf("Invalid position\n");
        return;
    }
    for (int i = position; i < arr->size - 1; i++) {
        arr->data[i] = arr->data[i + 1];
    }
    arr->size--;
}

// Function to search for an element in the array
int search(ArrayADT *arr, int element) {
    for (int i = 0; i < arr->size; i++) {
        if (arr->data[i] == element) {
            return i;
        }
    }
    return -1;
}

// Function to retrieve a single value from the array
int retrieveValue(ArrayADT *arr, int index) {
    if (index < 0 || index >= arr->size) {
        printf("Invalid index\n");
        return -1;
    }
    return arr->data[index];
}

// Function to retrieve a sub-array from the array
ArrayADT* retrieveSubArray(ArrayADT *arr, int from, int to) {
    if (from < 0 || to > arr->size || from >= to) {
        printf("Invalid indices\n");
        return NULL;
    }
    ArrayADT *subArray = createArray(to - from);
    for (int i = from; i < to; i++) {
        insertAtEnd(subArray, arr->data[i]);
    }
    return subArray;
}

// Function to free the memory allocated for the array
void freeArray(ArrayADT *arr) {
    free(arr->data);
    free(arr);
}

int main() {
    ArrayADT *arr = createArray(3); // Start with a small capacity

    // Insert more elements to exceed the initial capacity
    insertAtEnd(arr, 1);
    insertAtEnd(arr, 2);
    insertAtEnd(arr, 3);
    insertAtEnd(arr, 4); // This should trigger an increase in capacity
    insertAtEnd(arr, 5); // Add more elements to ensure capacity increase

    printf("Array after insertion: ");
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");

    // Demonstrating other operations
    insertAtPosition(arr, 20, 2);
    printf("Array after inserting 20 at position 2: ");
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");

    deleteFromEnd(arr);
    printf("Array after deleting from end: ");
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");

    deleteFromPosition(arr, 1);
    printf("Array after deleting from position 1: ");
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");

    int index = search(arr, 15);
    if (index != -1) {
        printf("Element 15 found at index %d\n", index);
    } else {
        printf("Element 15 not found\n");
    }

    int value = retrieveValue(arr, 1);
    if (value != -1) {
        printf("Element at index 1 is %d\n", value);
    }

    ArrayADT *subArray = retrieveSubArray(arr, 0, 3);
    printf("Sub-array from index 0 to 3: ");
    for (int i = 0; i < subArray->size; i++) {
        printf("%d ", subArray->data[i]);
    }
    printf("\n");

    freeArray(subArray);
    freeArray(arr);

    return 0;
}

String Representation in C

In C, strings are represented as arrays of characters terminated by a null character ('\0'). This null character indicates the end of the string.

Basic String Operations

#include <stdio.h>
#include <string.h>

int main() {
    char str1[20] = "Hello";
    char str2[20] = "World";

    // Concatenation without strcat
    int len1 = 0;
    while (str1[len1] != '\0') len1++;
    int len2 = 0;
    while (str2[len2] != '\0') len2++;
    for (int i = 0; i < len2; i++) {
        str1[len1 + i] = str2[i];
    }
    str1[len1 + len2] = '\0';
    printf("Concatenated string (without strcat): %s\n", str1);

    // Length without strlen
    int length = 0;
    while (str1[length] != '\0') {
        length++;
    }
    printf("Length of concatenated string (without strlen): %d\n", length);

    // Copy without strcpy
    char str3[20];
    int i = 0;
    while (str1[i] != '\0') {
        str3[i] = str1[i];
        i++;
    }
    str3[i] = '\0';
    printf("Copied string (without strcpy): %s\n", str3);

    // Comparison without strcmp
    int cmp = 0;
    for (int j = 0; str1[j] != '\0' || str2[j] != '\0'; j++) {
        if (str1[j] != str2[j]) {
            cmp = str1[j] - str2[j];
            break;
        }
    }
    if (cmp == 0) {
        printf("Strings are equal (without strcmp).\n");
    } else if (cmp > 0) {
        printf("str1 is greater than str2 (without strcmp).\n");
    } else {
        printf("str1 is less than str2 (without strcmp).\n");
    }

    // Reset strings for standard functions
    strcpy(str1, "Hello");
    strcpy(str2, "World");

    // Concatenation with strcat
    strcat(str1, str2);
    printf("Concatenated string (with strcat): %s\n", str1);

    // Length with strlen
    length = strlen(str1);
    printf("Length of concatenated string (with strlen): %d\n", length);

    // Copy with strcpy
    strcpy(str3, str1);
    printf("Copied string (with strcpy): %s\n", str3);

    // Comparison with strcmp
    cmp = strcmp(str1, str2);
    if (cmp == 0) {
        printf("Strings are equal (with strcmp).\n");
    } else if (cmp > 0) {
        printf("str1 is greater than str2 (with strcmp).\n");
    } else {
        printf("str1 is less than str2 (with strcmp).\n");
    }

    return 0;
}

Introduction to Pattern Matching

Pattern matching involves finding a substring, known as a pattern, within a larger string, known as the text. This is a fundamental operation in computer science, particularly in string processing and searching algorithms. The goal is to identify all occurrences of the pattern in the text efficiently.

A pattern is a sequence of characters that we aim to find within a larger string (the text). Patterns can vary in length and complexity, and they are specified by the user or the application that requires the search.

Examples:

Pattern: "abc", Text: "abcabcabc"
- The pattern "abc" appears at positions 0, 3, and 6 in the text.
Pattern: "test", Text: "this is a test string for testing pattern matching"
- The pattern "test" appears at positions 10 and 29 in the text.

Common Pattern Matching Algorithms

Naive Algorithm
Knuth-Morris-Pratt (KMP) Algorithm
Boyer-Moore Algorithm

Naive Algorithm

The Naive algorithm for pattern matching is the simplest method. It involves sliding the pattern over the text one character at a time and checking for a match at each position. If a match is found, the starting index is recorded. If not, the pattern is shifted one position to the right, and the process is repeated until the end of the text is reached.

Steps of the Naive Algorithm:

Start at the beginning of the text.
Check if the pattern matches the substring of the text starting at the current position.
If it matches, record the starting index.
Move the starting position one character to the right.
Repeat until the end of the text is reached.

Example:

Pattern: "abc", Text: "abcabcabc"

Start at position 0: Compare "abc" with "abc" - Match found.
Move to position 1: Compare "abc" with "bca" - No match.
Move to position 2: Compare "abc" with "cab" - No match.
Move to position 3: Compare "abc" with "abc" - Match found.
Move to position 4: Compare "abc" with "bca" - No match.
Move to position 5: Compare "abc" with "cab" - No match.
Move to position 6: Compare "abc" with "abc" - Match found.

The pattern "abc" is found at positions 0, 3, and 6 in the text.

Naive Pattern Matching Algorithm in C:

#include <stdio.h>
#include <string.h>

// Function to perform naive pattern matching
void naivePatternMatching(char *text, char *pattern) {
    int n = strlen(text);     // Length of the text
    int m = strlen(pattern);  // Length of the pattern

    // Slide the pattern over the text one character at a time
    for (int i = 0; i <= n - m; i++) {
        int j;

        // Check if the pattern matches the substring of the text starting at position i
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }

        // If the pattern matches, print the starting index
        if (j == m) {
            printf("Pattern found at index %d\n", i);
        }
    }
}

int main() {
    char text[] = "abcabcabc";
    char pattern[] = "abc";

    naivePatternMatching(text, pattern);
    return 0;
}

In this example, the naivePatternMatching function takes the text and pattern as inputs and prints all starting indices where the pattern is found in the text. The algorithm has a time complexity of O(n * m), where n is the length of the text and m is the length of the pattern. This makes it inefficient for large texts and patterns, but it is simple and easy to understand, making it useful for smaller inputs and educational purposes.

Introduction to Polynomials

A polynomial is a mathematical expression consisting of variables (also known as indeterminates) and coefficients. Polynomials are often represented as arrays in C.

Polynomial Addition

#include <stdio.h>

#define MAX 100

typedef struct {
    int coeff[MAX];
    int degree;
} Polynomial;

// Function to add two polynomials
Polynomial addPolynomials(Polynomial p1, Polynomial p2) {
    Polynomial result;
    result.degree = (p1.degree > p2.degree) ? p1.degree : p2.degree;

    for (int i = 0; i <= result.degree; i++) {
        result.coeff[i] = 0;
        if (i <= p1.degree) result.coeff[i] += p1.coeff[i];
        if (i <= p2.degree) result.coeff[i] += p2.coeff[i];
    }

    return result;
}

// Function to subtract two polynomials
Polynomial subtractPolynomials(Polynomial p1, Polynomial p2) {
    Polynomial result;
    result.degree = (p1.degree > p2.degree) ? p1.degree : p2.degree;

    for (int i = 0; i <= result.degree; i++) {
        result.coeff[i] = 0;
        if (i <= p1.degree) result.coeff[i] += p1.coeff[i];
        if (i <= p2.degree) result.coeff[i] -= p2.coeff[i];
    }

    return result;
}

// Function to multiply two polynomials
Polynomial multiplyPolynomials(Polynomial p1, Polynomial p2) {
    Polynomial result;
    result.degree = p1.degree + p2.degree;

    for (int i = 0; i <= result.degree; i++) {
        result.coeff[i] = 0;
    }

    for (int i = 0; i <= p1.degree; i++) {
        for (int j = 0; j <= p2.degree; j++) {
            result.coeff[i + j] += p1.coeff[i] * p2.coeff[j];
        }
    }

    return result;
}

// Function to divide two polynomials and get quotient and remainder
void dividePolynomials(Polynomial dividend, Polynomial divisor, Polynomial* quotient, Polynomial* remainder) {
    *quotient = (Polynomial){{0}, 0};
    *remainder = dividend;

    while (remainder->degree >= divisor.degree) {
        int deg_diff = remainder->degree - divisor.degree;
        int coeff_div = remainder->coeff[remainder->degree] / divisor.coeff[divisor.degree];

        Polynomial term = {{0}, deg_diff};
        term.coeff[deg_diff] = coeff_div;

        *quotient = addPolynomials(*quotient, term);
        Polynomial temp = multiplyPolynomials(term, divisor);
        *remainder = subtractPolynomials(*remainder, temp);
    }
}

// Function to print a polynomial
void printPolynomial(Polynomial p) {
    for (int i = p.degree; i >= 0; i--) {
        printf("%dx^%d", p.coeff[i], i);
        if (i > 0) printf(" + ");
    }
    printf("\n");
}

int main() {
    Polynomial p1 = {{5, 0, 10, 6}, 3}; // 6x^3 + 10x^2 + 5
    Polynomial p2 = {{1, 2, 4}, 2};     // 4x^2 + 2x + 1

    // Addition
    Polynomial sum = addPolynomials(p1, p2);
    printf("Sum of polynomials: ");
    printPolynomial(sum);

    // Subtraction
    Polynomial diff = subtractPolynomials(p1, p2);
    printf("Difference of polynomials: ");
    printPolynomial(diff);

    // Multiplication
    Polynomial product = multiplyPolynomials(p1, p2);
    printf("Product of polynomials: ");
    printPolynomial(product);

    // Division
    Polynomial quotient, remainder;
    dividePolynomials(p1, p2, &quotient, &remainder);
    printf("Quotient of polynomials: ");
    printPolynomial(quotient);
    printf("Remainder of polynomials: ");
    printPolynomial(remainder);

    return 0;
}

Introduction to Matrix Operations

Matrices are rectangular arrays of numbers, symbols, or expressions, arranged in rows and columns. Common matrix operations include addition, subtraction, multiplication, determinant, transpose, and inverse.

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Function to add two matrices
void addMatrices(int first[MAX][MAX], int second[MAX][MAX], int result[MAX][MAX], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            result[i][j] = first[i][j] + second[i][j];
        }
    }
}

// Function to subtract two matrices
void subtractMatrices(int first[MAX][MAX], int second[MAX][MAX], int result[MAX][MAX], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            result[i][j] = first[i][j] - second[i][j];
        }
    }
}

// Function to multiply two matrices
void multiplyMatrices(int first[MAX][MAX], int second[MAX][MAX], int result[MAX][MAX], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            result[i][j] = 0;
            for (int k = 0; k < n; k++) {
                result[i][j] += first[i][k] * second[k][j];
            }
        }
    }
}

// Function to transpose a matrix
void transposeMatrix(int matrix[MAX][MAX], int result[MAX][MAX], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            result[j][i] = matrix[i][j];
        }
    }
}

// Function to find the determinant of a matrix
int determinant(int matrix[MAX][MAX], int n) {
    int det = 0;
    if (n == 1) {
        return matrix[0][0];
    } else if (n == 2) {
        return (matrix[0][0] * matrix[1][1]) - (matrix[0][1] * matrix[1][0]);
    } else {
        int submatrix[MAX][MAX];
        for (int x = 0; x < n; x++) {
            int sub_i = 0;
            for (int i = 1; i < n; i++) {
                int sub_j = 0;
                for (int j = 0; j < n; j++) {
                    if (j == x) continue;
                    submatrix[sub_i][sub_j] = matrix[i][j];
                    sub_j++;
                }
                sub_i++;
            }
            det += (x % 2 == 0 ? 1 : -1) * matrix[0][x] * determinant(submatrix, n - 1);
        }
    }
    return det;
}

// Function to find the inverse of a matrix
void inverseMatrix(int matrix[MAX][MAX], float inverse[MAX][MAX], int n) {
    int det = determinant(matrix, n);
    if (det == 0) {
        printf("Inverse doesn't exist as determinant is zero.\n");
        return;
    }

    // Calculate the adjoint
    int adj[MAX][MAX];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int submatrix[MAX][MAX], sub_i = 0;
            for (int k = 0; k < n; k++) {
                if (k == i) continue;
                int sub_j = 0;
                for (int l = 0; l < n; l++) {
                    if (l == j) continue;
                    submatrix[sub_i][sub_j] = matrix[k][l];
                    sub_j++;
                }
                sub_i++;
            }
            adj[j][i] = (i + j) % 2 == 0 ? determinant(submatrix, n - 1) : -determinant(submatrix, n - 1);
        }
    }

    // Calculate the inverse
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            inverse[i][j] = (float) adj[i][j] / det;
        }
    }
}

// Function to print a matrix
void printMatrix(int matrix[MAX][MAX], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

// Function to print a float matrix
void printFloatMatrix(float matrix[MAX][MAX], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%.2f ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int n;
    int firstMatrix[MAX][MAX], secondMatrix[MAX][MAX], result[MAX][MAX];
    float inverse[MAX][MAX];

    // Input matrix size
    printf("Enter the size of the matrices (n x n): ");
    scanf("%d", &n);

    // Input first matrix
    printf("Enter elements of the first matrix (%d x %d):\n", n, n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &firstMatrix[i][j]);
        }
    }

    // Input second matrix
    printf("Enter elements of the second matrix (%d x %d):\n", n, n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &secondMatrix[i][j]);
        }
    }

    // Matrix addition
    addMatrices(firstMatrix, secondMatrix, result, n);
    printf("Sum of the matrices:\n");
    printMatrix(result, n);

    // Matrix subtraction
    subtractMatrices(firstMatrix, secondMatrix, result, n);
    printf("Difference of the matrices:\n");
    printMatrix(result, n);

    // Matrix multiplication
    multiplyMatrices(firstMatrix, secondMatrix, result, n);
    printf("Product of the matrices:\n");
    printMatrix(result, n);

    // Transpose of the first matrix
    transposeMatrix(firstMatrix, result, n);
    printf("Transpose of the first matrix:\n");
    printMatrix(result, n);

    // Determinant of the first matrix
    int det = determinant(firstMatrix, n);
    printf("Determinant of the first matrix: %d\n", det);

    // Inverse of the first matrix
    inverseMatrix(firstMatrix, inverse, n);
    printf("Inverse of the first matrix:\n");
    printFloatMatrix(inverse, n);

    return 0;
}

Introduction to Sparse Matrices

A sparse matrix is a matrix in which most of the elements are zero. Storing sparse matrices efficiently is important to save space and computational time. One common representation is the use of arrays to store non-zero elements and their positions.

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct {
    int row;
    int col;
    int value;
} Element;

typedef struct {
    int rows;
    int cols;
    int num;
    Element elements[MAX];
} SparseMatrix;

// Function to add two sparse matrices
SparseMatrix addSparseMatrices(SparseMatrix sm1, SparseMatrix sm2) {
    SparseMatrix result;
    result.rows = sm1.rows;
    result.cols = sm1.cols;
    result.num = 0;

    int i = 0, j = 0;
    while (i < sm1.num && j < sm2.num) {
        if (sm1.elements[i].row < sm2.elements[j].row ||
           (sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col < sm2.elements[j].col)) {
            result.elements[result.num++] = sm1.elements[i++];
        } else if (sm1.elements[i].row > sm2.elements[j].row ||
                  (sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col > sm2.elements[j].col)) {
            result.elements[result.num++] = sm2.elements[j++];
        } else {
            result.elements[result.num] = sm1.elements[i];
            result.elements[result.num++].value = sm1.elements[i++].value + sm2.elements[j++].value;
        }
    }

    while (i < sm1.num) {
        result.elements[result.num++] = sm1.elements[i++];
    }

    while (j < sm2.num) {
        result.elements[result.num++] = sm2.elements[j++];
    }

    return result;
}

// Function to subtract two sparse matrices
SparseMatrix subtractSparseMatrices(SparseMatrix sm1, SparseMatrix sm2) {
    SparseMatrix result;
    result.rows = sm1.rows;
    result.cols = sm1.cols;
    result.num = 0;

    int i = 0, j = 0;
    while (i < sm1.num && j < sm2.num) {
        if (sm1.elements[i].row < sm2.elements[j].row ||
           (sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col < sm2.elements[j].col)) {
            result.elements[result.num++] = sm1.elements[i++];
        } else if (sm1.elements[i].row > sm2.elements[j].row ||
                  (sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col > sm2.elements[j].col)) {
            result.elements[result.num] = sm2.elements[j++];
            result.elements[result.num++].value = -result.elements[result.num - 1].value;
        } else {
            result.elements[result.num] = sm1.elements[i];
            result.elements[result.num++].value = sm1.elements[i++].value - sm2.elements[j++].value;
        }
    }

    while (i < sm1.num) {
        result.elements[result.num++] = sm1.elements[i++];
    }

    while (j < sm2.num) {
        result.elements[result.num] = sm2.elements[j++];
        result.elements[result.num++].value = -result.elements[result.num - 1].value;
    }

    return result;
}

// Function to transpose a sparse matrix
SparseMatrix transposeSparseMatrix(SparseMatrix sm) {
    SparseMatrix result;
    result.rows = sm.cols;
    result.cols = sm.rows;
    result.num = sm.num;

    int index = 0;
    for (int col = 0; col < sm.cols; col++) {
        for (int i = 0; i < sm.num; i++) {
            if (sm.elements[i].col == col) {
                result.elements[index].row = sm.elements[i].col;
                result.elements[index].col = sm.elements[i].row;
                result.elements[index].value = sm.elements[i].value;
                index++;
            }
        }
    }

    return result;
}

// Function to multiply two sparse matrices
SparseMatrix multiplySparseMatrices(SparseMatrix sm1, SparseMatrix sm2) {
    SparseMatrix result;
    result.rows = sm1.rows;
    result.cols = sm2.cols;
    result.num = 0;

    if (sm1.cols != sm2.rows) {
        printf("Matrix multiplication not possible.\n");
        return result;
    }

    SparseMatrix sm2T = transposeSparseMatrix(sm2);
    int temp[MAX][MAX] = {0};

    for (int i = 0; i < sm1.num; i++) {
        for (int j = 0; j < sm2T.num; j++) {
            if (sm1.elements[i].col == sm2T.elements[j].col) {
                temp[sm1.elements[i].row][sm2T.elements[j].row] += sm1.elements[i].value * sm2T.elements[j].value;
            }
        }
    }

    for (int i = 0; i < sm1.rows; i++) {
        for (int j = 0; j < sm2.cols; j++) {
            if (temp[i][j] != 0) {
                result.elements[result.num].row = i;
                result.elements[result.num].col = j;
                result.elements[result.num++].value = temp[i][j];
            }
        }
    }

    return result;
}

// Function to print a sparse matrix
void printSparseMatrix(SparseMatrix sm) {
    printf("Row\tColumn\tValue\n");
    for (int i = 0; i < sm.num; i++) {
        printf("%d\t%d\t%d\n", sm.elements[i].row, sm.elements[i].col, sm.elements[i].value);
    }
}

int main() {
    SparseMatrix sm1 = {3, 3, 4, {{0, 0, 3}, {0, 2, 5}, {1, 1, 7}, {2, 2, 9}}};
    SparseMatrix sm2 = {3, 3, 3, {{0, 1, 6}, {1, 1, 3}, {2, 2, 8}}};

    // Addition
    SparseMatrix sum = addSparseMatrices(sm1, sm2);
    printf("Sum of sparse matrices:\n");
    printSparseMatrix(sum);

    // Subtraction
    SparseMatrix diff = subtractSparseMatrices(sm1, sm2);
    printf("Difference of sparse matrices:\n");
    printSparseMatrix(diff);

    // Transpose
    SparseMatrix trans = transposeSparseMatrix(sm1);
    printf("Transpose of the first sparse matrix:\n");
    printSparseMatrix(trans);

    // Multiplication
    SparseMatrix product = multiplySparseMatrices(sm1, sm2);
    printf("Product of sparse matrices:\n");
    printSparseMatrix(product);

    return 0;
}

Explanation with example of sparse matrix sum

This code defines a function addSparseMatrices that takes two sparse matrices (sm1 and sm2) and returns their sum as a new sparse matrix (result). A sparse matrix is a matrix in which most elements are zero, and it's stored efficiently by only keeping track of the non-zero elements.

Let's consider two sparse matrices sm1 and sm2 for the example.

Sparse Matrix 1 (sm1)

Row	Col	Value
0	1	3
1	2	5
2	0	7

Sparse Matrix 2 (sm2)

Row	Col	Value
0	1	4
1	2	-5
2	1	2

Step-by-Step Execution

Initialization:
```
 SparseMatrix result;
 result.rows = sm1.rows;
 result.cols = sm1.cols;
 result.num = 0;
```
- The result matrix is initialized with the same number of rows and columns as sm1 (and sm2 since they should have the same dimensions).
- result.num is set to 0, indicating that no elements have been added yet.
Merging Non-Zero Elements:
```
 int i = 0, j = 0;
 while (i < sm1.num && j < sm2.num) {
```
- Two pointers i and j are initialized to 0 to traverse the elements of sm1 and sm2, respectively.

Comparison and Addition:

 if (sm1.elements[i].row < sm2.elements[j].row ||
    (sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col < sm2.elements[j].col)) {
     result.elements[result.num++] = sm1.elements[i++];
 } else if (sm1.elements[i].row > sm2.elements[j].row ||
           (sm1.elements[i].row == sm2.elements[j].row && sm1.elements[i].col > sm2.elements[j].col)) {
     result.elements[result.num++] = sm2.elements[j++];
 } else {
     result.elements[result.num] = sm1.elements[i];
     result.elements[result.num++].value = sm1.elements[i++].value + sm2.elements[j++].value;
 }

This part of the code compares the current elements of sm1 and sm2 and decides which element to add to the result.
If sm1.elements[i] comes before sm2.elements[j], it is added to the result.
If sm2.elements[j] comes before sm1.elements[i], it is added to the result.
If both elements are at the same position (row and col), their values are added and stored in the result.

Let's see how this works with our example:

First elements (0,1,3) and (0,1,4):
- They are at the same position, so (0,1,3+4=7) is added to the result.
Next elements (1,2,5) and (1,2,-5):
- They are at the same position, so (1,2,5+(-5)=0) is not added to the result as the value is 0.
Next elements (2,0,7) and (2,1,2):
- (2,0,7) comes before (2,1,2), so it is added to the result.
Finally, (2,1,2) is added to the result.

Adding Remaining Elements:

 while (i < sm1.num) {
     result.elements[result.num++] = sm1.elements[i++];
 }

 while (j < sm2.num) {
     result.elements[result.num++] = sm2.elements[j++];
 }

If there are any remaining elements in sm1 or sm2, they are added to the result. In our case, all elements have already been processed.

Final Result

The resulting sparse matrix would be:

Row	Col	Value
0	1	7
2	0	7
2	1	2

Basic Problems

Second Largest Element: Write a program that takes an array of integers and finds the second largest element in the array. Ensure your solution works efficiently for both small and large arrays, and handles cases where there are duplicate elements or the array size is less than two.
Jagged Array Sum: Create a jagged array (array of arrays) where each row has a different number of columns. Write a program to calculate the sum of all elements in the jagged array and print the result. Ensure that your solution can handle varying row sizes and empty rows.
Array Element Deletion: Write a program that takes an array of integers and an integer value, then removes all occurrences of that value from the array. The program should shift the remaining elements to the left and reduce the size of the array accordingly, ensuring that no empty slots are left in the middle.
Transpose of a Matrix: Given an MxN matrix of integers, write a program to find the transpose of the matrix. The transpose of a matrix is obtained by swapping its rows and columns. Ensure your program works efficiently for both square and rectangular matrices.
Diagonal Sum of a Square Matrix: Write a program to calculate the sum of the primary and secondary diagonals of a square matrix. The primary diagonal runs from the top-left to the bottom-right, while the secondary diagonal runs from the top-right to the bottom-left. Ensure your program handles matrices of varying sizes.
Matrix Multiplication: Write a program to multiply two matrices and print the resultant matrix. The program should ensure that matrix multiplication is valid (i.e., the number of columns in the first matrix is equal to the number of rows in the second matrix) and handle matrices of varying dimensions.
Merge Two Sorted Arrays: Write a program that takes two sorted arrays of integers and merges them into a single sorted array. Ensure your solution handles arrays of different lengths and merges the arrays in O(n) time complexity, where n is the total number of elements in both arrays.
Find Missing Number in Array: Given an array containing n-1 distinct numbers taken from the range 1 to n, write a program to find the missing number in the array. Ensure your solution works efficiently without using extra space.
Check for Magic Square: Write a program to check if a given 2D square matrix of integers is a magic square. A magic square is a grid where the sums of the numbers in each row, each column, and both main diagonals are the same. The program should handle matrices of varying sizes.
Find Peak Element in Array: Write a program to find a peak element in an array of integers. A peak element is an element that is greater than or equal to its neighbors. The program should return the index of any peak element and handle arrays of different lengths.
Frequency Count in Array: Write a program to count the frequency of each element in an array of integers. The program should output each element along with its frequency and handle arrays of varying sizes, ensuring efficient performance for large arrays.

Two Pointer Technique

The two-pointer technique is a common algorithmic approach used to solve various problems in computer science, especially in array and string manipulation. The idea is to use two pointers to traverse the data structure, allowing the algorithm to check pairs of elements or maintain a window of elements efficiently. This technique is often used to reduce the time complexity of an algorithm from $O(n^2)$ to $O(n)$ by avoiding nested loops.

One Pointer Left Fixed While Right is Probing

Longest Substring Without Repeating Characters: Given a string, write a program to find the length of the longest substring without repeating characters. Use one pointer to fix the start of the substring and another pointer to expand the substring by probing further into the string, adjusting the pointers as necessary.
Count Subarrays with Sum Less than K: Given an array of integers and an integer K, write a program to count the number of subarrays where the sum of the elements is less than K. Use one pointer to fix the start of the subarray and another pointer to expand the subarray by probing further, adjusting the pointers based on the sum condition.

Left and Right Moving Towards Each Other

Two Sum Sorted Array: Given a sorted array of integers and a target value, write a program to find two numbers such that they add up to a specific target number. Use two pointers starting from the beginning and end of the array, and move them towards each other until the target sum is found.
Palindrome Check: Given a string, write a program to check if it is a palindrome. Use two pointers, one starting at the beginning and the other at the end of the string, moving towards each other while comparing characters until they meet in the middle.

Sliding Window Technique

The sliding window technique is an efficient way to solve problems involving subarrays or substrings. Instead of using nested loops to iterate over all possible subarrays, a window of fixed or variable size slides over the data structure to maintain a subset of elements that can be processed incrementally. This technique reduces the time complexity to $O(n)$ by maintaining the window and updating it as it moves.

Fixed Sliding Window

Maximum Sum Subarray of Size K: Given an array of integers and an integer K, write a program to find the maximum sum of a subarray of size K. Use the sliding window technique to maintain a window of size K and slide it across the array, updating the sum as you go.
Average of Subarrays of Size K: Given an array of integers and an integer K, write a program to find the average of all subarrays of size K. Use the sliding window technique to maintain the sum of elements in the window and compute the average as the window slides across the array.

Variable Sliding Window (Either Left or Right Boundary Can Move)

Smallest Subarray with Sum Greater than S: Given an array of integers and an integer S, write a program to find the length of the smallest subarray with a sum greater than S. Use the sliding window technique where the right boundary expands to increase the sum and the left boundary contracts to find the minimum length subarray.
Longest Substring with At Most K Distinct Characters: Given a string and an integer K, write a program to find the length of the longest substring that contains at most K distinct characters. Use the sliding window technique to expand the right boundary to include new characters and contract the left boundary to maintain at most K distinct characters.

Solutions

Sure, here are the same programs with comments added to explain the code:

1. Second Largest Element

#include <stdio.h>
#include <limits.h>

// Function to find the second largest element in an array
void findSecondLargest(int arr[], int n) {
    if (n < 2) {
        printf("Array size is less than two.\n");
        return;
    }

    int first = INT_MIN, second = INT_MIN;

    // Traverse the array to find the largest and second largest elements
    for (int i = 0; i < n; i++) {
        if (arr[i] > first) {
            second = first; // Update second largest
            first = arr[i]; // Update largest
        } else if (arr[i] > second && arr[i] != first) {
            second = arr[i]; // Update second largest
        }
    }

    if (second == INT_MIN) {
        printf("There is no second largest element.\n");
    } else {
        printf("The second largest element is %d\n", second);
    }
}

int main() {
    int arr[] = {12, 35, 1, 10, 34, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    findSecondLargest(arr, n);
    return 0;
}

2. Jagged Array Sum

#include <stdio.h>
#include <stdlib.h>

int main() {
    int rows = 3; // Number of rows in the jagged array
    int *jagged[rows];
    int sizes[] = {3, 2, 4}; // Number of columns in each row

    // Allocating and initializing jagged array
    jagged[0] = (int[]) {1, 2, 3};
    jagged[1] = (int[]) {4, 5};
    jagged[2] = (int[]) {6, 7, 8, 9};

    int totalSum = 0; // Variable to store the total sum of elements
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < sizes[i]; j++) {
            totalSum += jagged[i][j]; // Calculate sum of all elements
        }
    }

    printf("Total sum of elements in jagged array: %d\n", totalSum);
    return 0;
}

3. Array Element Deletion

#include <stdio.h>

// Function to delete all occurrences of a value from the array
void deleteElement(int arr[], int *n, int value) {
    int i, j;
    for (i = 0; i < *n; i++) {
        if (arr[i] == value) {
            // Shift elements to the left to overwrite the deleted element
            for (j = i; j < *n - 1; j++) {
                arr[j] = arr[j + 1];
            }
            (*n)--; // Decrease the size of the array
            i--; // Check the current index again after shifting
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 2, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int value = 2;

    deleteElement(arr, &n, value);

    printf("Array after deletion: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

4. Transpose of a Matrix

#include <stdio.h>

// Function to transpose a matrix
void transpose(int arr[][3], int m, int n, int result[][3]) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            result[j][i] = arr[i][j]; // Swap rows and columns
        }
    }
}

int main() {
    int arr[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int result[3][3];
    transpose(arr, 3, 3, result);

    printf("Transpose of the matrix:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", result[i][j]);
        }
        printf("\n");
    }
    return 0;
}

5. Diagonal Sum of a Square Matrix

#include <stdio.h>

// Function to calculate the sum of primary and secondary diagonals
void diagonalSum(int arr[][3], int n) {
    int primaryDiagonalSum = 0, secondaryDiagonalSum = 0;
    for (int i = 0; i < n; i++) {
        primaryDiagonalSum += arr[i][i]; // Sum of primary diagonal
        secondaryDiagonalSum += arr[i][n - 1 - i]; // Sum of secondary diagonal
    }
    printf("Primary Diagonal Sum: %d\n", primaryDiagonalSum);
    printf("Secondary Diagonal Sum: %d\n", secondaryDiagonalSum);
}

int main() {
    int arr[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    diagonalSum(arr, 3);
    return 0;
}

6. Matrix Multiplication

#include <stdio.h>

// Function to multiply two matrices
void multiplyMatrices(int first[][2], int second[][2], int result[][2], int r1, int c1, int r2, int c2) {
    if (c1 != r2) {
        printf("Matrix multiplication not possible\n");
        return;
    }

    // Initialize the result matrix with zeros
    for (int i = 0; i < r1; i++) {
        for (int j = 0; j < c2; j++) {
            result[i][j] = 0;
            for (int k = 0; k < c1; k++) {
                result[i][j] += first[i][k] * second[k][j]; // Multiply and accumulate
            }
        }
    }
}

int main() {
    int first[2][2] = {
        {1, 2},
        {3, 4}
    };
    int second[2][2] = {
        {5, 6},
        {7, 8}
    };
    int result[2][2];

    multiplyMatrices(first, second, result, 2, 2, 2, 2);

    printf("Resultant matrix after multiplication:\n");
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            printf("%d ", result[i][j]);
        }
        printf("\n");
    }
    return 0;
}

7. Merge Two Sorted Arrays

#include <stdio.h>

// Function to merge two sorted arrays
void merge(int arr1[], int n1, int arr2[], int n2, int result[]) {
    int i = 0, j = 0, k = 0;

    // Merge elements from both arrays in sorted order
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            result[k++] = arr1[i++];
        } else {
            result[k++] = arr2[j++];
        }
    }

    // Copy remaining elements from arr1
    while (i < n1) {
        result[k++] = arr1[i++];
    }

    // Copy remaining elements from arr2
    while (j < n2) {
        result[k++] = arr2[j++];
    }
}

int main() {
    int arr1[] = {1, 3, 5, 7};
    int arr2[] = {2, 4, 6, 8};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int result[n1 + n2];

    merge(arr1, n1, arr2, n2, result);

    printf("Merged array: ");
    for (int i = 0; i < n1 + n2; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    return 0;
}

8. Find Missing Number in Array

#include <stdio.h>

// Function to find the missing number in the array
int findMissingNumber(int arr[], int n) {
    int total = (n * (n + 1)) / 2; // Calculate sum of first n natural numbers
    for (int i = 0; i < n - 1; i++) {
        total -= arr[i]; // Subtract each element from the total
    }
    return total; // The remaining value is the missing number
}

int main() {
    int arr[] = {1, 2, 4, 6, 3, 7, 8};
    int

 n = sizeof(arr) / sizeof(arr[0]) + 1; // Total number of elements (n)
    int missing = findMissingNumber(arr, n);
    printf("Missing number is %d\n", missing);
    return 0;
}

9. Check for Magic Square

#include <stdio.h>
#include <stdbool.h>

// Function to check if a given 2D matrix is a magic square
bool isMagicSquare(int arr[][3], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[0][i]; // Calculate the sum of the first row
    }

    // Check sums of all rows
    for (int i = 1; i < n; i++) {
        int rowSum = 0;
        for (int j = 0; j < n; j++) {
            rowSum += arr[i][j];
        }
        if (rowSum != sum) {
            return false;
        }
    }

    // Check sums of all columns
    for (int i = 0; i < n; i++) {
        int colSum = 0;
        for (int j = 0; j < n; j++) {
            colSum += arr[j][i];
        }
        if (colSum != sum) {
            return false;
        }
    }

    // Check sum of primary diagonal
    int diag1Sum = 0, diag2Sum = 0;
    for (int i = 0; i < n; i++) {
        diag1Sum += arr[i][i];
        diag2Sum += arr[i][n - 1 - i];
    }

    if (diag1Sum != sum || diag2Sum != sum) {
        return false;
    }

    return true;
}

int main() {
    int arr[3][3] = {
        {2, 7, 6},
        {9, 5, 1},
        {4, 3, 8}
    };

    if (isMagicSquare(arr, 3)) {
        printf("The matrix is a magic square.\n");
    } else {
        printf("The matrix is not a magic square.\n");
    }
    return 0;
}

10. Find Peak Element in Array

#include <stdio.h>

// Function to find a peak element in the array
int findPeakElement(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        // Check if the current element is a peak element
        if ((i == 0 || arr[i] >= arr[i - 1]) && (i == n - 1 || arr[i] >= arr[i + 1])) {
            return i;
        }
    }
    return -1; // This should never be reached if array has at least one element
}

int main() {
    int arr[] = {1, 3, 20, 4, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    int peakIndex = findPeakElement(arr, n);
    if (peakIndex != -1) {
        printf("Peak element is at index %d with value %d\n", peakIndex, arr[peakIndex]);
    } else {
        printf("No peak element found.\n");
    }
    return 0;
}

11. Frequency Count in Array

#include <stdio.h>
#include <stdlib.h>

// Function to count the frequency of each element in the array
void countFrequency(int arr[], int n) {
    int *frequency = (int *)calloc(n, sizeof(int));

    // Count frequency of each element
    for (int i = 0; i < n; i++) {
        frequency[arr[i]]++;
    }

    // Print frequency of each element
    printf("Element frequency:\n");
    for (int i = 0; i < n; i++) {
        if (frequency[arr[i]] != 0) {
            printf("%d: %d times\n", arr[i], frequency[arr[i]]);
            frequency[arr[i]] = 0; // Set to 0 to avoid duplicate printing
        }
    }

    free(frequency); // Free allocated memory
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    countFrequency(arr, n);
    return 0;
}

12. Longest Substring Without Repeating Characters

#include <stdio.h>
#include <string.h>

int longestSubstringWithoutRepeatingChars(char *str) {
    int n = strlen(str);
    int maxLength = 0;
    int start = 0; // Pointer to fix the start of the substring
    int charIndex[256]; // Array to store the last index of each character

    // Initialize all elements to -1
    for (int i = 0; i < 256; i++) {
        charIndex[i] = -1;
    }

    for (int end = 0; end < n; end++) {
        // If character is already seen, move the start pointer
        if (charIndex[str[end]] >= start) {
            start = charIndex[str[end]] + 1;
        }
        // Update the last index of the character
        charIndex[str[end]] = end;
        // Update the maximum length of substring
        maxLength = maxLength > (end - start + 1) ? maxLength : (end - start + 1);
    }

    return maxLength;
}

int main() {
    char str[] = "abcabcbb";
    int length = longestSubstringWithoutRepeatingChars(str);
    printf("Length of the longest substring without repeating characters: %d\n", length);
    return 0;
}

13. Count Subarrays with Sum Less than K

#include <stdio.h>

int countSubarraysWithSumLessThanK(int arr[], int n, int k) {
    int count = 0;
    int start = 0; // Pointer to fix the start of the subarray
    int sum = 0;

    for (int end = 0; end < n; end++) {
        sum += arr[end]; // Expand the window by adding the current element

        // While sum is not less than k, contract the window from the start
        while (sum >= k && start <= end) {
            sum -= arr[start++];
        }

        // All subarrays ending at 'end' and starting from 'start' to 'end' are valid
        count += (end - start + 1);
    }

    return count;
}

int main() {
    int arr[] = {1, 11, 2, 3, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 10;
    int count = countSubarraysWithSumLessThanK(arr, n, k);
    printf("Number of subarrays with sum less than %d: %d\n", k, count);
    return 0;
}

14. Two Sum Sorted Array

#include <stdio.h>
#include <stdbool.h>

bool twoSumSortedArray(int arr[], int n, int target, int *num1, int *num2) {
    int left = 0;
    int right = n - 1;

    while (left < right) {
        int sum = arr[left] + arr[right];

        if (sum == target) {
            *num1 = arr[left];
            *num2 = arr[right];
            return true;
        } else if (sum < target) {
            left++; // Move the left pointer to the right
        } else {
            right--; // Move the right pointer to the left
        }
    }

    return false; // No two numbers found
}

int main() {
    int arr[] = {2, 7, 11, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    int num1, num2;

    if (twoSumSortedArray(arr, n, target, &num1, &num2)) {
        printf("Numbers found: %d and %d\n", num1, num2);
    } else {
        printf("No two numbers found that add up to %d\n", target);
    }

    return 0;
}

15. Palindrome Check

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool isPalindrome(char *str) {
    int left = 0;
    int right = strlen(str) - 1;

    while (left < right) {
        if (str[left] != str[right]) {
            return false; // Characters do not match
        }
        left++;
        right--;
    }

    return true; // String is a palindrome
}

int main() {
    char str[] = "racecar";
    if (isPalindrome(str)) {
        printf("The string \"%s\" is a palindrome.\n", str);
    } else {
        printf("The string \"%s\" is not a palindrome.\n", str);
    }

    return 0;
}

16. Maximum Sum Subarray of Size K

#include <stdio.h>

int maxSumSubarrayOfSizeK(int arr[], int n, int k) {
    int maxSum = 0;
    int currentSum = 0;

    // Calculate the sum of the first window of size K
    for (int i = 0; i < k; i++) {
        currentSum += arr[i];
    }

    maxSum = currentSum;

    // Slide the window from start to end of the array
    for (int i = k; i < n; i++) {
        currentSum += arr[i] - arr[i - k]; // Add the next element and remove the first element of the previous window
        if (currentSum > maxSum) {
            maxSum = currentSum; // Update the maximum sum
        }
    }

    return maxSum;
}

int main() {
    int arr[] = {2, 1, 5, 1, 3, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    int maxSum = maxSumSubarrayOfSizeK(arr, n, k);
    printf("Maximum sum of a subarray of size %d: %d\n", k, maxSum);
    return 0;
}

17. Average of Subarrays of Size K

#include <stdio.h>

void averageOfSubarraysOfSizeK(int arr[], int n, int k) {
    double currentSum = 0;

    // Calculate the sum of the first window of size K
    for (int i = 0; i < k; i++) {
        currentSum += arr[i];
    }

    // Slide the window from start to end of the array
    for (int i = k; i < n; i++) {
        printf("Average of subarray [%d, %d]: %.2f\n", i - k + 1, i, currentSum / k);
        currentSum += arr[i] - arr[i - k]; // Add the next element and remove the first element of the previous window
    }

    // Print the average of the last subarray
    printf("Average of subarray [%d, %d]: %.2f\n", n - k, n - 1, currentSum / k);
}

int main() {
    int arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    averageOfSubarraysOfSizeK(arr, n, k);
    return 0;
}

18. Smallest Subarray with Sum Greater than S

#include <stdio.h>

int smallestSubarrayWithSumGreaterThanS(int arr[], int n, int s) {
    int minLength = n + 1;
    int currentSum = 0;
    int start = 0;

    for (int end = 0; end < n; end++) {
        currentSum += arr[end]; // Expand the window by adding the current element

        // Contract the window from the start while the current sum is greater than S
        while (currentSum > s) {
            if (end - start + 1 < minLength) {
                minLength = end - start + 1; // Update the minimum length
            }
            currentSum -= arr[start++]; // Remove the start element from the current sum
        }
    }

    return minLength == n + 1 ? 0 : minLength;
}

int main() {
    int arr[] = {2, 1, 5, 2, 3, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int s = 7;
    int minLength = smallestSubarrayWithSumGreaterThanS(arr, n, s);
    if (minLength == 0) {
        printf("No subarray found with sum greater than %d\n", s);
    } else {
        printf("Length of the smallest subarray with sum greater than %d: %d\n", s, minLength);
    }
    return 0;
}

19. Longest Substring with At Most K Distinct Characters

#include <stdio.h>
#include <string.h>

int longestSubstringWithAtMostKDistinctChars(char *str, int k) {
    int n = strlen(str);
    int maxLength = 0;
    int start = 0; // Pointer to fix the start of the substring
    int charCount[256] = {0}; // Array to store the count of each character
    int distinctCount = 0; // Count of distinct characters in the current window

    for (int end = 0; end < n; end++) {
        if (charCount[str[end]] == 0) {
            distinctCount++; // Increment distinct character count
        }
        charCount[str[end]]++;

        // While distinct character count exceeds K, contract the window from the start
        while (distinctCount > k) {
            charCount[str[start]]--;
            if (charCount[str[start]] == 0) {
                distinctCount--; // Decrement distinct character count
            }
            start++;
        }

        // Update the maximum length of substring
        maxLength = maxLength > (end - start + 1) ? maxLength : (end - start + 1);
    }

    return maxLength;
}

int main() {
    char str[] = "eceba";
    int k = 2;
    int length = longestSubstringWithAtMostKDistinctChars(str, k);
    printf("Length of the longest substring with at most %d distinct characters: %d\n", k, length);
    return 0;
}

Command Palette

Comments

More from this blog

Implementing an Enhanced Array ADT

Instructions

String Representation in C

Basic String Operations

Introduction to Pattern Matching

Examples:

Common Pattern Matching Algorithms

Naive Algorithm

Steps of the Naive Algorithm:

Example:

Naive Pattern Matching Algorithm in C:

Introduction to Polynomials

Polynomial Addition

Introduction to Matrix Operations

Introduction to Sparse Matrices

Sparse Matrix 1 (sm1)

Sparse Matrix 2 (sm2)

Basic Problems

Two Pointer Technique

One Pointer Left Fixed While Right is Probing

Left and Right Moving Towards Each Other

Sliding Window Technique

Fixed Sliding Window

Variable Sliding Window (Either Left or Right Boundary Can Move)

Solutions

1. Second Largest Element

2. Jagged Array Sum

3. Array Element Deletion

4. Transpose of a Matrix

5. Diagonal Sum of a Square Matrix

6. Matrix Multiplication

7. Merge Two Sorted Arrays

8. Find Missing Number in Array

9. Check for Magic Square

10. Find Peak Element in Array

11. Frequency Count in Array

12. Longest Substring Without Repeating Characters

13. Count Subarrays with Sum Less than K

14. Two Sum Sorted Array

15. Palindrome Check

16. Maximum Sum Subarray of Size K

17. Average of Subarrays of Size K

18. Smallest Subarray with Sum Greater than S

19. Longest Substring with At Most K Distinct Characters