Program to Count Subarrays with K Odd Numbers.

Given an integer array containing n elements and an integer value k, we need to write a program to count the number of continuous subarrays in the given array that contain k number of odd numbers. 

Example:

Input: arr[] = {3, 1, 2, 1, 1}, k = 3
Output: 2
Explanation:
Subarrays with 3 odd numbers are {3, 1, 2, 1} and {1, 2, 1, 1}. 

Input: arr[] = {2, 1, 9, 3, 1}, k = 2
Output: 4
Explanation:
Subarrays with 2 odd numbers are 
{1, 9} {9, 3} {3, 1} {2, 1, 9} 

This problem can be solved by multiple approaches, let's discuss each of them one by one with efficiency.

Approach 1: Brute Force.

The brute force approach involves considering all possible subarrays of the given array and checking each subarray to see if it contains exactly k odd numbers.

Below is the C++ code implementation for this approach.

//C++ code to Count Subarrays with K Odd Numbers.
//Brute force
#include<iostream>
#include <vector>
using namespace std;

//function to return count of subarrays
//with k odd numbers
int countOddSubarrays(vector<int>& nums, int k) {
    int n = nums.size();
    int count = 0;
    
    //traverse for all possible subarrays
    for (int i = 0; i < n; i++) {
        int oddCount = 0;
        for (int j = i; j < n; j++) {
            if (nums[j] % 2 == 1) {
                oddCount++;
            }
            if (oddCount == k) {
                count++;
            }
        }
    }

    return count;
}

int main(){
    vector<int> nums = {1, 2, 1, 1, 4, 1};
    int k = 3;

    cout << countOddSubarrays(nums, k);
}

Output:

4

Time Complexity: O(n^2), because we are using the nested loop to check all possible subarrays.

Space Complexity: O(1), as it does not use any extra space to solve this problem.

Approach 2: Sliding Window Approach.

In this approach, we begin by initializing two pointers, start and end, both pointing to the first element of the array. Additionally, we set count and ans to zero. 

The next step involves traversing the array using the end pointer. During this traversal, we increment the count variable if the element is odd. We then slide the window to the right until the count becomes equal to k.

With each step, we update the ans variable to keep track of the number of subarrays containing exactly k odd integers. Eventually, we return the value of ans.

To calculate the number of subarrays with exactly k odd integers, we compute the difference between the number of subarrays with less than k odd integers and the number of subarrays with at most k-1 odd integers. Remarkably, we can leverage the same subArray function to compute both of these values efficiently.

Below is the C++ code implementation for the above approach.

//C++ code to Count Subarrays with K Odd Numbers.
//Sliding window approach
#include<iostream>
#include <vector>
using namespace std;

int subArray(vector<int>& nums, int k) {
    int count = 0, ans = 0, start = 0, end = 0;
    int n = nums.size();

    // Sliding window approach
    while(end<n){
        if(nums[end]%2==1){
            count++;
        }
        // Shrink the window until the count 
        //becomes less than or equal to K
        while(count>k){
            if(nums[start]%2==1){
                count--;
            }
            start++;
        }
        ans += end-start+1;
        end++;
    }
    return ans;
}
// Function to count the number of 
//subarrays with K odd numbers
int countOddSubarrays(vector<int>& nums, int k) {
    /*
    difference between number of subarrays with at most k-1
    odd elements with number of subarrays with at most k
    odd elements
    */
    return subArray(nums, k) - subArray(nums, k - 1);
}

int main(){
    vector<int> nums = {2, 1, 9, 3, 1};
    int k = 2;

    cout << countOddSubarrays(nums, k);
}

Output:

4

Time Complexity: O(n)

Space Complexity: O(1)

(getButton) #text=(Sliding Window Explanation with Example) #icon=(link) #color=(#2339bd)

Program to find third distinct maximum number in the array.

Given an integer array nums[] of size n, we need to find the third distinct maximum number in an integer array nums. If the third maximum number does not exist, we need to return the maximum number present in the array.

Note: If the array has less than three distinct maximum numbers, then we need to return the maximum number from the array.

Let's understand the problem with an example:

Example 1:
Input: nums[] = {3, 5, 1, 8, 5, 4, 2, 9}
Output: 5

Explanation: 

The distinct maximum numbers in the array are 9, 8, and 5. 
So, the third distinct maximum number is 5. 

Example 2:
Input: nums[] = {2, 8}
Output: 8

Explanation: 

No third element is present in the given array 
so return the maximum element that is 8

Example 3:
Input: nums[] = {2, 2, 3, 1}
Output: 1

Explanation: 

The distinct maximum numbers in the array are 3, 2, and 1. 

So, the third distinct maximum number is 1. 

There are multiple approaches by which we can solve this problem and here we are going to discuss each of them one by one.

Approach 1: Using Sorting.

The brute force approach to solve this problem is by arranging the given array in descending order which will make our task easier to find the third distinct element.

Steps-by-step algorithm:

Step 1: We can sort the array in descending order.

Step 2: Then, we can iterate through the sorted array and keep track of distinct maximum numbers.

Step 3: If we find the third distinct maximum number, we return it. Otherwise, we return the maximum number.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//function
int thirdMax(vector<int>& nums) {
    //arrange the vector in descending order
    sort(nums.begin(), nums.end(), greater<int>());

    int count = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[i - 1]) {
            count++;
        }
        if (count == 3) {
            return nums[i];
        }
    }
    //return max if no third distinct max is found
    return nums[0];
}

int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2, 9};

    cout<< thirdMax(nums);

    return 0;
}

Output:

5

Time Complexity: The sorting operation using sort takes O(n * log n) time, where n is the number of elements in the input array. After sorting, we iterate through the sorted array once to find the third distinct maximum number. This step takes O(n) time. So, the overall time complexity is O(n * log n + n) = O(n * log n).

Space Complexity: The space complexity is O(1) as we are not using any additional data structure. 

Approach 2: Using Set.

As we know a set container is used to store unique elements in a specific order and allows for efficient insertion, deletion, and retrieval of elements based on their values. 

Step-by-step algorithm:

Step 1: We can use a set to keep track of distinct numbers while traversing the array.

Step 2: If the set size is less than 3 after traversing the array, it means we have less than three distinct maximum numbers, so we return the maximum number present in the array.

Step 3: If the set size is greater than or equal to 3, we return the third element from the set.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum using set
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

//function
int thirdMax(vector<int>& nums) {
    set<int> distinctNums;

    //traverse the array and atmost
    //store three elements in the set
    for (int num : nums) {
        distinctNums.insert(num);
        if (distinctNums.size() > 3) {
            distinctNums.erase(distinctNums.begin());
        }
    }
    //size of set is less than 3 
    //no third distinct element present
    if(distinctNums.size() < 3)
    //return max element present in set
       return *(--distinctNums.end());
    //size of set is equal to 3 
    //top most element of set is the third distinct
    else
       return *(distinctNums.begin());
}

int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2, 9};

    cout<< thirdMax(nums);

    return 0;
}

Output:

5

Note: The expression *(--distinctNums.end()) is used to access the last element in a set. 

Time Complexity: The set insertion and deletion operations have an average time complexity of O(log n) then we iterate through the entire input array once, performing set operations on each element, so the overall time complexity is O(n * log n).

Space Complexity: The space required for the set depends on the number of distinct elements in the array, which is at most 3 in this case. Therefore, the space complexity is O(1), as it remains constant regardless of the input size.

Approach 3: Using three variables. (Most Optimized).

The idea for this optimized approach comes from the requirement to find the third distinct maximum number in a single pass through the array with O(n) time complexity. To achieve this efficiently, we need to keep track of the first, second, and third distinct maximum numbers while traversing the array.

Step-by-step algorithm:

Step 1: We declare three variables (firstMax, secondMax, thirdMax) to keep track of the first, second, and third distinct maximum numbers, respectively.

Step 2: We initialize them with the minimum possible value (INT_MIN).

Step 3: We traverse the input array and update these variables as follows:

• If the current number is greater than firstMax, we update thirdMax with secondMax, secondMax with firstMax, and then update firstMax with the current number.
• If the current number is between firstMax and secondMax, we update thirdMax with secondMax and secondMax with the current number.
• If the current number is between secondMax and thirdMax, we update thirdMax with the current number.

Step 4: After the loop, if thirdMax remains equal to the initial value (INT_MIN), it means there are less than three distinct maximum numbers in the array, and we return firstMax (the maximum number). Otherwise, we return thirdMax.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum
#include <bits/stdc++.h>
using namespace std;

int thirdMax(vector<int>& nums) {
    int firstMax = INT_MIN;
    int secondMax = INT_MIN;
    int thirdMax = INT_MIN;

    for (int num : nums) {
        //current number is greater
        if (num > firstMax) {
            thirdMax = secondMax;
            secondMax = firstMax;
            firstMax = num;
        } 
        //current number is between first and second max
        else if (num < firstMax && num > secondMax) {
            thirdMax = secondMax;
            secondMax = num;
        } 
        //current number is between second and third max
        else if (num < secondMax && num > thirdMax) {
            thirdMax = num;
        }
    }

    return (thirdMax == INT_MIN) ? firstMax : thirdMax;
}


int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2};

    cout<< thirdMax(nums);

    return 0;
}

Output:

4

Time Complexity: The time complexity of this solution is O(n) as we are able to find the required answer just in a single traversal. 

Space Complexity: The space complexity is constant O(1) as we are only using three variables for solving this problem. 

I hope you are able to understand all three approaches to solving this problem. We have covered all three approaches in sequence order from brute force to optimized one.  

Check Strictly Increasing Array by Removing at most One Element in C++.

Given an integer array arr[] of size n, the task is to check if the given array can be made strictly increasing after removing at most one element from the array. Return true if it is possible to make the given array strictly increasing else return false. Note: If the given array is already strictly increasing then simply return true.

• A strictly increasing array means that for every nums[i] and nums[i + 1], the relationship nums[i] < nums[i + 1] holds.

Example:

Input: arr[] = {1, 2, 12, 5, 7}
Output: true
Explanation: By removing 12 from index 2, the array becomes {1, 2, 5, 7} 
which is strictly increasing.

Input: arr[] = {1, 4, 5, 3, 2}
Output: false
Explanation: By removing any element of the array it is not possible to make 
it strictly increasing.

Input: arr[] = {1, 2, 2, 5, 5}
Output: false

This problem can be solved using multiple approaches and here we are going to understand each of them one by one starting from brute force to optimized one.

Approach 1: Brute Force.

In this approach, we are going to remove each element one by one and then we will check if the resulting array is strictly increasing or not.

Step-by-step explanation:

Step 1: Define a helper function to check if the given array is strictly increasing or not. Return true if the array is strictly increasing, otherwise false.

Step 2: Iterate through the array and simulate removing each element one by one.

Step 3: For each removed element, check if the resulting array is strictly increasing using the helper function.

Step 4: Push the removed element back inside the array if the condition is not satisfied.

Step 5: If any array condition is strictly increasing, we return true, indicating that the array can be made strictly increasing by removing one element.

Step 6: If no such array condition is found even after trying to remove each element, we return false. 

Below is the C++ code implementation of the above approach:

//C++ Brute Force Approach to check strictly increasing array 
#include<iostream>
#include <vector>
using namespace std;

//helper function to check if the array is 
//strictly increasing or not
bool isStrictlyIncreasing(vector<int>& nums) {
    int n = nums.size();
    bool isIncreasing = true;
    
    for (int i = 1; i < n; i++) {
        if (nums[i] <= nums[i - 1]) {
            isIncreasing = false;
            break;
        }
    }

    return isIncreasing;
}

bool canBeIncreasing(vector<int>& nums) {
    int n = nums.size();

    for (int i = 0; i < n; i++) {
        int removedElement = nums[i];
        // Simulate removing the element
        nums.erase(nums.begin() + i); 
        //calling helper function to check
        if (isStrictlyIncreasing(nums)) {
            return true;
        }
        // Put back the removed element
        nums.insert(nums.begin() + i, removedElement); 
    }

    return false;
}

int main(){

    vector<int> nums{1, 2, 12, 5, 7};

    if(canBeIncreasing(nums))
       cout<<"True";
    else
       cout<<"False";   
       
    return 0;
}

Output:

True

Time Complexity: The time complexity of this approach is O(n^2), where n is the number of elements in the array. For each element, we check if the resulting array is strictly increasing, which takes O(n) time. As we do this for each element, the overall time complexity becomes O(n^2).

Space Complexity: The space complexity is O(1) as we use only a constant amount of extra space for variables, and we modify the input array in place without using any additional data structures.

Approach 2: Optimized Approach.

Using the brute force approach we are getting a time complexity of O(n^2) but we can easily optimize the above approach and solve in O(n) time complexity.

Step-by-step explanation:

Step 1: Initialize a variable count to keep track of the number of elements that violate the strictly increasing condition.

Step 2: Iterate through the array from index 1 to the end. If the current element is less than or equal to the previous element, it means it violates the strictly increasing condition.

Step 3: Increment the count and check if it becomes greater than 1. If yes, it means we need to remove more than one element to make the array strictly increasing, so we return false.

Step 4: If the count is 1, it means we found one violating element. We then try removing it and checking if the array becomes strictly increasing.

Step 5: To remove the violating element, we have two choices:

• If the current element is greater than the element before the previous element (nums[i] > nums[i - 2]), we remove the current element by setting it equal to the previous element.
• Otherwise, we remove the previous element by setting it equal to the current element.

Step 6: Continue iterating through the array, and if we find any more violating elements, we return false.

Step 7: If we successfully iterate through the entire array without finding any more violating elements, it means we can make the array strictly increasing by removing exactly one element, so we return true.

C++ code implementation of the above approach:

//C++ Optimized Approach to check strictly increasing array 
#include<iostream>
#include <vector>
using namespace std;

//function to check strictly increasing
bool canBeIncreasing(vector<int>& nums) {
    int n = nums.size();
    // Count of violating elements
    int count = 0; 

    for (int i = 1; i < n; i++) {
        if (nums[i] <= nums[i - 1]) {
            count++;
            if (count > 1) {
                return false;
            }

            // Check if removing the current element makes 

            //the array strictly increasing
            if (i == 1 || nums[i] > nums[i - 2]) {
                nums[i - 1] = nums[i];
            } else {
                nums[i] = nums[i - 1];
            }
        }
    }
    return true;
}


int main(){

    vector<int> nums{1, 2, 12, 5, 7};

    if(canBeIncreasing(nums))
       cout<<"True";
    else
       cout<<"False";   

    return 0;
}

Output:

True

Time Complexity: The time complexity of this solution is O(n), where n is the number of elements in the array. We iterate through the array only once.

Space Complexity: The space complexity is O(1) as we use only a constant amount of extra space for variables.

C++ Program for Concatenation of Array.

Given an integer array nums of length n, create a new array ans of length 2n such that ans is the concatenation of two nums arrays. 

• ans[i] = nums[i] and ans[i+n] = nums[i]
• 0 <= i < n

Example:
Input: nums = [3, 2, 4]
Output: ans = [3, 2, 4, 3, 2, 4]

Input: nums = [1, 3, 2, 4]
Output: ans = [1, 3, 2, 4, 1, 3, 2, 4]

Explaination: 

ans = [nums[0], nums[1], nums[2], nums[3], nums[0], nums[1], nums[2], nums[3]]

Algorithm 1:

• Declare two integer arrays nums and ans of size n and 2n respectively.

• Read the values of the array nums from the user.

• Use a loop to copy the elements of nums into the first half of ans, i.e., from ans[0] to ans[n-1].

• Use another loop to copy the elements of nums into the second half of ans, i.e., from ans[n] to ans[2n-1].

• Print the elements of ans to the console.

C++ Code Implementation:

//C++ Program to concatenation of array
#include<iostream>
using namespace std;

//Concatenation function
void getConcatenation(int n, int nums[], int ans[]){
     // copying elements of nums into the first half of ans
   for(int i = 0; i < n; i++) {
      ans[i] = nums[i];
   }

   // copying elements of nums into the second half of ans
   for(int i = 0; i < n; i++) {
      ans[i+n] = nums[i];
   }
}
int main(){

    int nums[] = {1, 3, 2, 8};
    //size of given array
    int size = sizeof(nums)/sizeof(nums[0]);
    int ans[size*2];

    getConcatenation(size, nums, ans);

    for(int i = 0; i < 2*size; i++){
        cout<<ans[i]<<" ";
    }
}

Output:

1 3 2 8 1 3 2 8

• Time Complexity: O(n) where is the size of the given array.
• Space Complexity: O(2n) where 2n is the size of the answer array.

Algorithm 2:

In this algorithm, we are iterating over the output array ans and assigning nums[i % n] to ans[i], where % is the modulo operator. This ensures that we repeat the elements of nums from the beginning once we reach the end of the array. 

C++ Code Implementation:

//C++ Program to concatenation of array
#include<iostream>
#include<vector>
using namespace std;

//Concatenation function
vector<int> concatenateArrays(int n, int nums[]) {
   
    vector<int> ans(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        ans[i] = nums[i % n];
    }
    return ans;
}
 
int main(){

    int nums[] = {1, 3, 2, 8};
    //size of given array
    int size = sizeof(nums)/sizeof(nums[0]);

    vector<int> ans  = concatenateArrays(size, nums);

    for(int i = 0; i < 2*size; i++){
        cout<<ans[i]<<" ";
    }
}

Output:

1 3 2 8 1 3 2 8

• Time Complexity: O(n) where is the size of the given array.
• Space Complexity: O(2n) where 2n is the size of the answer array.

Detect Cycle in a Linked List in C++.

Given the head of a linked list, detect if the given linked list contains a cycle. Return true if there exists a cycle else return false. Below is an example of two linked lists containing cycles.

Approach 1: Using Hashmap.

In this approach, you are going to insert all the nodes one by one inside a hashmap, and whenever you found a condition that a particular node is already present in the hashmap then it means there exists a cycle so return true.

C++ Solution Code:

/*C++ Program detect cycle in a linked list using hashmap*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
//Function to detect cycle of linked list
bool detectCycle(ListNode *head){
    unordered_set<ListNode*> hp;
    //loop to check cycle
    while(head != NULL){

        if(hp.find(head) != hp.end())
           return true;
        hp.insert(head);   
        head = head->next;   
    }
    return false;
}
int main(){

    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next = head; //cycle formation

    bool check = detectCycle(head);

    if(check)
      cout<<"Linked List contains a cycle.";
    else
      cout<<"Linked List does not contain a cycle.";

    return 0;
}

Output:

Linked List contains a cycle.

• Time Complexity: O(n) where n is the number of nodes present.
• Space Complexity: O(n) because we are using one extra hashmap.

Approach 2: Two Pointer Approach (Slow and Fast Pointer).

In this approach, you need to use two pointers and one pointer will move slower than the other pointer. If the linked list contains a cycle then slow and fast pointers must meet at some point and if they meet each other at any point it means there exists a cycle.

• Initialize two pointers, slow and fast with the head of the linked list.
• Traverse the list, every time the slow pointer moves one step, and the faster moves two steps
• If there is a cycle then both slow and fast pointers will meet at some point, return true if they meet else return false.

C++ Solution Code:

/*C++ Program detect cycle in a linked list using 
two pointer approach*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
//Function to detect cycle of linked list
bool detectCycle(ListNode *head){
    
    if(head == NULL) return false;

    ListNode* slow = head;
    ListNode* fast = head;

    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast) return true; //cycle detected
    }
    return false;
}
int main(){

    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next = head; //cycle formation

    bool check = detectCycle(head);

    if(check)
      cout<<"Linked List contains a cycle.";
    else
      cout<<"Linked List does not contain a cycle.";

    return 0;
}

Output:

Linked List contains a cycle.

• Time Complexity: O(n) where n is the number of nodes in the linked list.
• Space Complexity: O(1)

Related Articles:

• Convert Binary Linked List to Integer.

• Find the Middle of the Singly Linked List in C++.

• Reverse a Singly Linked List in C++.

• Merge Two Sorted Linked List in C++.

• Intersection Point of Two Linked Lists in C++.