Python Program to Subtract two Matrices.

Matrix subtraction is a fundamental operation in linear algebra and is often required in various scientific and computational applications. In this article, we'll explore how to subtract two matrices using Python programming.

In matrix subtraction, elements of one matrix are subtracted from their corresponding elements in another matrix of the same dimensions. The result is a new matrix with dimensions identical to the original matrices being subtracted. 

Quick Tip: Ensure matrices have the same dimensions for subtraction (m x n).

Matrix Subtraction Program in Python.

Step-by-step Algorithm:

• Define two matrices A and B, each represented as nested lists in Python.

• Create a new matrix to store the result of the subtraction.

• Subtract corresponding elements of matrices A and B to obtain the elements of the resultant matrix.

• Use nested loops to iterate through each element in the matrices and perform subtraction.

Python Code:

# Python code for matrix subtraction
def subtract_matrices(matrix_A, matrix_B):
    result_matrix = []
    for i in range(len(matrix_A)):
        row = []
        for j in range(len(matrix_A[0])):
            row.append(matrix_A[i][j] - matrix_B[i][j])
        result_matrix.append(row)
    return result_matrix

# Example usage
matrix_A = [[1, 2, 3],
            [4, 5, 6],
            [7, 8, 9]]

matrix_B = [[9, 8, 7],
            [6, 5, 4],
            [3, 2, 1]]

result = subtract_matrices(matrix_A, matrix_B)
print("Resultant Matrix after subtraction:")
for row in result:
    print(row)

Output:

Resultant Matrix after subtraction:
[-8, -6, -4]
[-2, 0, 2]
[4, 6, 8]

• Time Complexity: O(m x n) where m is the number of rows and n is the number of columns.
• Space Complexity: O(m x n) because we need extra space to store the resultant matrix.

Python Program to Add Two Matrices.

In Python programming, performing matrix operations holds importance in various computational tasks. Adding two matrices is a fundamental operation, often encountered in scientific computing, data analysis, and machine learning. Let's understand the efficient way to perform this operation in Python.

Matrix Addition in Python.

Matrix addition is possible only when the matrices meet specific conditions related to their dimensions. For two matrices A and B to be added together (A + B = C), they must satisfy the following conditions:

• Both matrices must have the same number of rows and columns.
• If matrix A has dimensions m x n (m rows and n columns), matrix B must also have dimensions m x n.

Python Code for Adding Two Matrices.

# Python Code for Matrix Addition
def add_matrices(matrix1, matrix2):
    # Check if matrices have the same dimensions
    if len(matrix1) != len(matrix2) or len(matrix1[0]) != len(matrix2[0]):
        return "Matrices should have the same dimensions for addition"

    result = []
    for i in range(len(matrix1)):
        row = []
        for j in range(len(matrix1[0])):
            row.append(matrix1[i][j] + matrix2[i][j])
        result.append(row)
    return result

# Example matrices for addition
matrix_A = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

matrix_B = [
    [9, 8, 7],
    [6, 5, 4],
    [3, 2, 1]
]

# Calling the function to add matrices
resultant_matrix = add_matrices(matrix_A, matrix_B)
print("Resultant Matrix after Addition:")
for row in resultant_matrix:
    print(row)

Output:

Resultant Matrix after Addition:
[10, 10, 10]
[10, 10, 10]
[10, 10, 10]

Explanation: The add_matrices() function takes two matrices as input parameters and checks if they have the same dimensions. If the matrices have the same dimensions, it iterates through corresponding elements of the matrices, performs element-wise addition, and constructs the resultant matrix.

• Time Complexity: O(m x n)
• Space Complexity: O(m x n)

Python Program to Print 2D Matrix.

Printing a 2D matrix in Python is a fundamental operation, often encountered in various data manipulation and algorithmic tasks. A 2D matrix, also known as a 2D array, represents data in a grid format consisting of rows and columns. Python offers several methods to effectively display and print a 2D matrix.

Let's explore different methods to print a 2D matrix in Python:

Method 1: Using Nested Loops.

One of the simplest ways to print a 2D matrix is by utilizing nested loops to iterate through rows and columns.

Python Code:

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Using nested loops to print the matrix
for row in matrix:
    for element in row:
        print(element, end=" ")  
    print()  # Move to the next line after printing a row

Output:

1 2 3
4 5 6 
7 8 9 

Method 2: Using List Comprehension.

Python's list comprehension offers a concise way to print a 2D matrix.

Python Code:

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Using list comprehension to print the matrix
[print(*row) for row in matrix]

Output:

1 2 3
4 5 6 
7 8 9 

Method 3: Using NumPy Library.

The NumPy library provides powerful functionalities for handling multi-dimensional arrays, including 2D matrices.

Python Code:

import numpy as np

matrix = np.array([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
])

# Printing the NumPy matrix
print(matrix)

Output:

1 2 3
4 5 6 
7 8 9 

Python Program to Count Subarray with given Sum.

Given an array of integers, write a Python program to determine the number of subarrays that sum up to a given target sum. 

Example:

Input: arr = [1, 2, 3, 2, 1] sum = 3
Output: Number of Subarrays: 3

Explanation:
There are 3 subarrays sum up to the target sum of 3:
[1, 2]
[3]
[2, 1]

There are multiple approaches to solving the problem of counting subarrays with a given sum, and here we going to discuss a few of them starting from a brute force approach to more optimized solutions.

Approach 1: Brute Force.

In this brute-force method, we explore all possible subarrays within the given array and calculate the sum of each subarray to identify the count of subarrays that match the desired sum.

Algorithm:

• Use two nested loops to generate all possible subarrays.
• Calculate the sum of each subarray.
• Count the number of subarrays with the given sum.

Python Code:

# Python code to count subarrays for given sum (Brute Force)
def count_subarrays(arr, target_sum):
    count = 0
    n = len(arr)
    
    for start in range(n):
        current_sum = 0
        for end in range(start, n):
            current_sum += arr[end]
            if current_sum == target_sum:
                count += 1
    
    return count

arr = [1, 2, 3, 2, 1]
sum = 3
print("Number of Subarrays:", count_subarrays(arr, sum))

Output:

Number of Subarrays: 3

• Time Complexity: As we are checking for all possible subarrays using a nested loop the time complexity of this approach is O(n^2) where n is the length of the array.

• Space Complexity: We are not using any extra space in this approach so the space complexity is O(1).

Approach 2: Prefix Sum.

The prefix sum approach optimizes the solution by leveraging cumulative sums and a hash map to efficiently count subarrays with the given sum. It reduces the time complexity significantly compared to the brute-force method.

Algorithm:

• Calculate the cumulative sum of the array elements.
• Maintain a hash map to store the cumulative sums and their frequencies.
• Determine the count of subarrays with the given sum using the hash map.

Python Code:

# Python code to count subarray for given sum using prefix sum
def count_subarrays(arr, target_sum):
    count = 0
    prefix_sum = {0: 1}
    current_sum = 0
    
    for num in arr:
        current_sum += num
        if current_sum - target_sum in prefix_sum:
            count += prefix_sum[current_sum - target_sum]
        
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
    
    return count

arr = [1, 4, 20, 3, 10, 5]
sum = 33
print("Number of Subarrays:", count_subarrays(arr, sum))

Output:

Number of Subarrays: 1

• Time Complexity: We are traversing the array once so the time complexity is O(n).

• Space Complexity: We are using the hash map to store cumulative sums so the space complexity is O(n).

Approach 3: Sliding Window Technique.

This is the most optimized approach to count the subarray with a given sum. The sliding window technique optimizes the solution further by using two pointers to maintain a window within the array. It dynamically adjusts the window based on the current sum, minimizing unnecessary calculations and achieving a linear time complexity.

Algorithm:

• Use two pointers, typically named left and right, to represent the window boundaries.
• Initialize left and right to the start of the array.
• Expand the window by moving the right pointer to the right.
• Adjust the window based on the current sum.
• If the current sum exceeds the desired sum or target sum, shrink the window by moving the left pointer to the right.
• Continue this process until the sum becomes less than or equal to the target sum.
• Whenever the current sum matches the desired sum, increment the count to track the subarrays that satisfy the condition.
• Continue sliding the window until the right pointer reaches the end of the array.

Python Code:

# Python code count subarrays using sliding window algorithm
def count_subarrays(arr, target_sum):
    count = 0
    current_sum = 0
    left = 0

    for right in range(len(arr)):
        current_sum += arr[right]

        while current_sum > target_sum and left <= right:
            current_sum -= arr[left]
            left += 1

        if current_sum == target_sum:
            count += 1

    return count

arr = [1, 4, 20, 3, 10, 5, 15]
sum = 33
print("Number of Subarrays:", count_subarrays(arr, sum))

Output:

Number of Subarrays: 2

• Time Complexity: In this case where the array elements are non-negative or non-zero, this technique achieves a linear time complexity, typically O(n), making it highly efficient for larger datasets.

• Space Complexity: We are not using any extra space in this sliding window approach so space complexity is O(1).

You can learn the Sliding Window Algorithm in more detail from one of our article: Sliding Window Algorithm with Example.

Python Program to Find Missing Integer in an Array.

Problem Statement.

Given an integer array of size n-1 and the array containing distinct numbers in a range of [1, n]. The task is to write a Python program to find the missing number from the array.

Example:

Input: arr = [1, 2, 3, 4, 6]
Output: Missing Number is 5

Input: arr = [3, 1, 2, 5, 7, 6]
Output: Missing Number is 4

There are multiple approaches to finding the missing number in an array and here we are going to discuss three of them.

• Using Set.
• Using XOR.
• Using Summation.

Python Program to Find Missing Number Using Set.

In this approach, we are using a set data structure to efficiently identify the missing number in a given sequence or array.

Algorithm:

• Step 1: Convert the given sequence or array into a set for efficient lookup operations.

• Step 2: Create a set containing all the numbers in the expected range or sequence.

• Step 3: Subtract the set of given numbers from the set of expected numbers. 

• Step 4: The remaining elements in the expected set would be the missing number.

Python Code:

def find_missing_integer(arr):
    n = len(arr) + 1  # Including the missing integer

    full_set = set(range(1, n + 1))
    arr_set = set(arr)

    missing_integer = full_set - arr_set

    return missing_integer.pop()

arr = [1, 2, 3, 4, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 5

• Time Complexity: The time complexity of the above approach is O(n) because the construction of the set takes O(n) time and the subtraction of one set with another also takes O(n) time.

• Space Complexity: The space complexity is O(n) as it requires additional space to store the sets of expected and given numbers.

Python Program to Find Missing Number of Array Using XOR.

The XOR approach utilizes the properties of the XOR operation to find the missing number in an array. XORing any number with itself results in 0 so all identical elements cancel out each other.

Algorithm:

• Step 1: Iterate through the given array and XOR all the elements with each other.

• Step 2: XOR all the numbers from 1 to n to obtain a cumulative XOR value.

• Step 3: XOR the cumulative XOR value from Step 1 with the XOR value from Step 2.

• Step 4: The result will be the missing number in the array.

Python Code:

# Python code implementation to find missing number
def find_missing_integer(arr):
    n = len(arr) + 1  
    xor_full = 0
    xor_arr = 0

    # XOR of all numbers from 1 to n
    for i in range(1, n + 1):
        xor_full ^= i

    # XOR of all numbers in the array
    for num in arr:
        xor_arr ^= num

    missing_integer = xor_full ^ xor_arr
    return missing_integer

arr = [3, 1, 2, 5, 7, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 4

• Time Complexity: O(n) because we have to iterate through the array to perform XOR operations.

• Space Complexity: O(1) because we have used a constant amount of extra space for variables.

Python Program to Find Missing Number of Array Using Summation.

In this approach, we are using math formulas to find the sum of the first n natural numbers. Then we subtract the sum of the array with the sum of the natural number and it will return us the missing number.

Algorithm:

• Step 1: Iterate through the given array and calculate the sum of all the elements.

• Step 2: Determine the expected sum of all the numbers in the sequence from 1 to n. This can be calculated using the formula: (n * (n+1))/2.

• Step 3: Subtract the sum of the given numbers from the expected sum. The result will be the missing number.

Python Code:

# Python code to find missing number using math
def find_missing_integer(arr):
    n = len(arr) + 1  

    expected_sum = n * (n + 1) // 2

    actual_sum = sum(arr)
    missing_integer = expected_sum - actual_sum

    return missing_integer

arr = [3, 1, 2, 5, 7, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 4

• Time Complexity: O(n) because we have to iterate through the array to calculate the sum of array elements.

• Space Complexity: O(1) as no extra space is required in this approach to find the missing number.

Python Programg to Find Kth Largest Number in an Array.

Given an array arr[] of size n and a number k, the task is to write a Python program to find the kth largest element from the array. Note that the value of k is always less than the size of the array and the array contain all distinct element.

Example:

Input: arr = [2, 5, 1, 6, 3, 9]  k = 2
Output: 6
Explanation: The second largest element in the array in 6

Input: arr = [12, 5, 1, 6, 3, 9, 10]  k = 3
Output: 9
Explanation: The third largest element in the array in 9

Kth Largest Element in an Array Using Sorting.

In this approach, we first sort the entire array and then retrieve the kth largest element from the sorted array.

Algorithm:

• Sort the entire array in descending order using an efficient sorting algorithm like Quicksort.

• Return the kth element from the sorted array, which represents the kth largest number.

Python Code:

def kth_largest(arr, k):
    arr.sort(reverse=True)
    return arr[k - 1]

arr = [2, 5, 1, 6, 3, 9]
k = 2
print("Kth largest element is",kth_largest(arr, k))  

Output:

Kth largest element is 6

• Time Complexity: O(n log n) for sorting + O(1) for retrieving kth element = O(n log n).

• Space Complexity: Depends on the sorting algorithm, generally O(log n) for efficient algorithms, up to O(n) in worst-case scenarios.

Kth Largest Element in an Array Using Heap.

In this approach, we are going to use min-heap to efficiently find the kth largest element without sorting the entire array.

Algorithm:

• Create a min-heap of size k and insert the first k elements from the array into the heap.

• The root of the min-heap will always be the smallest element among the k elements.

• For the remaining elements in the array, compare each element with the root of the heap.

• If the element is larger than the root, replace the root with this element and re-heapify the min-heap to maintain its structure.

• After traversing through the entire array, the root of the min-heap will be the kth largest element.

Python Code:

import heapq

def kth_largest_heap(arr, k):
    heap = arr[:k]
    heapq.heapify(heap)
    
    for num in arr[k:]:
        if num > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, num)
    
    return heap[0]

arr =[12, 5, 1, 6, 3, 9, 10]  
k = 3
print("Kth largest element is", kth_largest_heap(arr, k))  

Output:

Kth largest element is 9

Time Complexity:

Building the initial min-heap with the first k elements takes O(k) time. For the remaining (n-k) elements, each insertion and re-heapification operation takes O(log k) time. Therefore, the overall time complexity is O(n log k).

Space Complexity:

The space complexity is O(k) to maintain the min-heap of size k.

Quickselect Algorithm to Find the Kth Largest Number.

Quickselect is an algorithm used to find the kth smallest or largest element in an unsorted array. It's an optimization of the quicksort algorithm.

Algorithm:

• Choose a pivot element from the array. Rearrange the elements in the array such that elements smaller than the pivot are on the left, and elements greater than the pivot are on the right.

• Based on the position of the pivot after partitioning, the pivot's index is compared to k - 1.

• If the pivot index is equal to k - 1, then the pivot is the kth largest element. Return the pivot.

• If the pivot index is less than k - 1, the kth largest element must be in the right subarray. Recur for the right subarray.

• If the pivot index is greater than k - 1, the kth largest element must be in the left subarray. Recur for the left subarray.

• Repeat the process until the pivot's index is equal to k - 1.

Python Code:

# Python code to find kth largest element from array
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] >= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quickselect(arr, low, high, k):
    if low <= high:
        pivot_index = partition(arr, low, high)     

        if pivot_index == k - 1:
            return arr[pivot_index]
        elif pivot_index > k - 1:
            return quickselect(arr, low, pivot_index - 1, k)
        else:
            return quickselect(arr, pivot_index + 1, high, k)

def kth_largest(arr, k):
    return quickselect(arr, 0, len(arr) - 1, k)

arr = [3, 6, 8, 9, 12, 51, 13] 
k = 3
print("Kth largest element is", kth_largest(arr, k))

Output:

Kth largest element is 12

• Time Complexity: The average time complexity is O(n) but in the worst case, Quickselect's time complexity can degrade to O(n^2).

• Space Complexity: Quickselect has a space complexity of O(log n) for the recursive call stack due to its recursive nature.

Python Program to Left Rotate an Array.

Problem Statement: You are given an array of integers and an integer K. Implement a Python program to perform a left rotation on the array K times. Left rotation means that each array element will be shifted K places to the left, and the elements overflowing from the left side will be placed at the end of the array.

Example:

Input: 
Given array: [1, 2, 3, 4, 5, 6]
Number of rotations: 2

Output:
[3, 4, 5, 6, 1, 2]

Explanation:

The array [1, 2, 3, 4, 5, 6] is rotated twice to the left. In each rotation, the elements shift to the left by two positions. After the first rotation, the array becomes [2, 3, 4, 5, 6, 1]. After the second rotation, it becomes [3, 4, 5, 6, 1, 2]. 

Left Rotation of an Array

Python Program to Left Rotation Using Brute Force Approach.

The simplest approach to left-rotate an array is to perform one rotation at a time for the specified number of positions. 

Brute Force Algorithm:

1. This Algorithm involves an outer loop that runs K times to perform the specified number of rotations.
2. Inside each iteration of the loop, the following steps are executed to perform a single left rotation:
   • Store the first element of the array in a temporary variable to prevent its value from being overwritten.
   • Shift all other elements one position to the left. This is done by iterating through the array and assigning each element the value of the element at the next index.
   • Place the temporary variable (the original first element) at the end of the array, effectively completing one left rotation.
3. This process of rotating the array K times is repeated for the specified number of rotations.

Example Illustration:

Python Code:

# Python code to left rotate array (Brute Force)
def left_rotate_array(arr, k):
     length = len(arr)
     for i in range(k):
           # store the first element
           temp = arr[0]
           
           # Shift all other elements to the left
           for i in range(length - 1):
                  arr[i] = arr[i + 1]
           
            # Place the first element at the end
            arr[length - 1] = temp

# Example usage:
given_array = [1, 2, 3, 4, 5]
rotations = 2

print("Original array:", given_array)
left_rotate_array(given_array, rotations)
print(f"After {rotations} left rotations:", given_array)

Output:

Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]

• Time Complexity: O(n * d) where n is the length of the array and d is the number of positions to rotate. This can be inefficient for large arrays or a high number of rotations.

• Space Complexity: O(1) no extra space is required to rotate the array using this method.

Python Program to Rotate an Array Using Slicing.

The array left rotation algorithm using slicing in Python involves manipulating the original array to create a left-rotated version without individually moving each element.

Algorithm Explanation:

To handle scenarios where the number of rotations ('k') exceeds the array's length, take the modulo of 'k' with the array's length. This step ensures that 'k' remains within the range of the array's length.

• Create a new list called rotated_array by using Python's list slicing.

• Slice the original array (arr) from index 'k' to the end (arr[k:]). This extracts the elements that need to be moved to the beginning after rotation.

• Concatenate (+) this slice with the portion of the array from the start to index 'k' (arr[:k]). This captures the elements that should be moved to the end after rotation.

• This combination represents the left-rotated version of the array.

• Update the original array (arr) with the values from the rotated_array.

• Iterate through the rotated_array and assign each value to the corresponding index in the original array.

• This step replaces the elements in the original array with the left-rotated elements.

Example Illustration:

This slicing approach efficiently handles left rotation without individually moving each element, making it a concise and Pythonic way to achieve the desired rotation.

Python Code:

def left_rotate_array(arr, k):
    length = len(arr)
    k = k % length  # Ensure k is within array length
    
    # Slicing to perform left rotation
    rotated_array = arr[k:] + arr[:k]
    
    # Update original array with rotated values
    for i in range(length):
        arr[i] = rotated_array[i]

# Example usage:
given_array = [1, 2, 3, 4, 5]
rotations = 2

print("Original array:", given_array)
left_rotate_array(given_array, rotations)
print(f"After {rotations} left rotations:", given_array)

Output:

Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]

• Time Complexity: Slicing in Python takes (n) time complexity, where n is the number of elements being sliced and concatenated.

• Space Complexity: O(n) because we have created a temporary array for rotation.

Python Program to Rotate an Array Using Reversal Algorithm.

The reversal algorithm involves three steps to perform left rotation on an array.

Reversal Algorithm:

• Reverse the elements from the start of the array up to the k index.

• Reverse the elements from the k index to the end of the array.

• Reverse the entire array to obtain the final left-rotated array.

Example Illustration:

Python Code:

def reverse_array(arr, start, end):
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1

def left_rotate_array(arr, k):
    length = len(arr)
    k = k % length  # Ensure k is within array length for multiple rotations
    
    # Reverse the first part: from start to k
    reverse_array(arr, 0, k - 1)
    
    # Reverse the second part: from k to end
    reverse_array(arr, k, length - 1)
    
    # Reverse the entire array
    reverse_array(arr, 0, length - 1)

# Example usage:
given_array = [1, 2, 3, 4, 5]
rotations = 2

print("Original array:", given_array)
left_rotate_array(given_array, rotations)
print(f"After {rotations} left rotations:", given_array)

Output:

Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]

• Time Complexity: For each reversal operation it will take O(n) time so the overall time complexity will be O(n) where n is the number of elements.

• Space Complexity: The algorithm uses a constant amount of extra space O(1).

So these are a few approaches to left-rotate an array in Python. Each approach has different space and time complexity so you can choose the most optimized one for your solution.