fbpx

Tag Archives: Array

HomeWisdom Sprouts IT Training Hub  > Blog  > Array
delete consecutive words sequence using stack in C++
Author Tejal Tarde Categories Data Structures, Interview Preparation, Stack

Delete Consecutive Same Words In A Sequence Of Words Using Stack In C++

In this article, we will address the problem of identifying and removing consecutive similar words from a sequence of strings using C++. We will walk you through the algorithm and provide a sample C++ code to implement this solution.

Problem Statement

Given a sequence of n strings, the task is to check if any two similar words come together and then destroy each other then print the number of words left in the sequence after this pairwise destruction.

Algorithm Overview

In this solution we are using Stack data structure.

  • Create an empty stack to store words.
  • Initialize a variable ‘count’ to 0 to keep track of the number of words left.
  • Iterate through each word in the input sequence:
    • If the stack is not empty and the current word is equal to the word at the top of the stack, it indicates a pair of similar words. Pop the word from the stack (destroy it) and continue to the next word.
    • If the stack is empty or the current word is different from the word at the top of the stack, push the current word onto the stack to preserve it.
  • After processing all the words in the sequence, the stack will contain the remaining words that survived destruction.
  • The size of the stack at this point represents the number of words left.
  • Return the value of ‘count’ as the result.

Implementation in C++

C++
#include<bits/stdc++.h>
using namespace std;

int removeConsecutiveSame(vector<string> inputSequence) {
    int sequenceSize = inputSequence.size();
    for (int i = 0; i < sequenceSize - 1;) {
        if (inputSequence[i] == inputSequence[i + 1]) {
            inputSequence.erase(inputSequence.begin() + i);
            inputSequence.erase(inputSequence.begin() + i);
            if (i > 0) {
                i--;
            }
            sequenceSize -= 2;
        } else {
            i++;
        }
    }
    return inputSequence.size();
}

int main() {
    vector<string> inputSequence = { "ab", "aa", "aa", "bcd", "ab" };
    cout << "Number of words left: " << removeConsecutiveSame(inputSequence) << endl;
    return 0;
}

Conclusion

In solving this problem, we have utilized a stack data structure to efficiently identify and remove consecutive similar words from a sequence of strings. The algorithm preserves non-consecutive words while eliminating consecutive duplicates, ultimately yielding the count of words remaining in the sequence as the result.

Kth largest element in an array
Author ws_admin Categories Data Structures, Interview Preparation

Kth Largest Element In An Array

When working with arrays, it’s often necessary to find the Kth largest element, where K is a positive integer. While there are efficient algorithms like the QuickSelect algorithm for this task, let’s start by understanding the brute force method – a straightforward approach to solving this problem. In this blog, we’ll walk you through the process step by step and provide you with a code snippet to help you grasp the concept.

Algorithm Overview

The brute force method to find the Kth largest element involves iterating through the array, comparing each element with the rest, and keeping track of the Kth largest element encountered so far. Let’s break down the approach:

  1. Initialize a variable to keep track of the Kth largest element.
  2. Loop through the array.
  3. For each element, compare it with the current Kth largest element.
  4. If the element is greater than the current Kth largest element, update the Kth largest element.
  5. Continue this process until you have iterated through the entire array.
  6. The final value of the Kth largest element will be the desired result.

Implementation in C++

C++
#include <iostream>
#include <vector>

using namespace std;

int findKthLargest(vector<int>& nums, int k) {
    // Ensure that k is a valid index within the array
    if (k < 1 || k > nums.size()) {
        cout << "Invalid value of k. Exiting..." << endl;
        exit(EXIT_FAILURE);
    }

    // Basic selection sort to find the kth largest element
    for (int i = 0; i < k; ++i) {
        int max_idx = i;
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[j] > nums[max_idx]) {
                max_idx = j;
            }
        }
        // Swap the elements
        int temp = nums[i];
        nums[i] = nums[max_idx];
        nums[max_idx] = temp;
    }

    return nums[k - 1];
}

int main() {
    vector<int> arr = {3, 1, 7, 5, 8, 2, 4, 6};
    int k = 4;

    int kth_largest = findKthLargest(arr, k);
    cout << "The " << k << "th largest element is: " << kth_largest << endl;

    return 0;
}

Conclusion

While the brute force method is straightforward and easy to understand, it may not be the most efficient solution for large arrays. In such cases, algorithms like QuickSelect offer better time complexity. However, understanding the brute force method lays the foundation for grasping more complex algorithms. We hope this blog has provided you with a clear understanding of how to find the Kth largest element using brute force. Feel free to explore more advanced algorithms for optimizing this task further.