Flood Fill Algorithm

The flood fill problem is a way to fill a region of connected pixels with a new colour, starting from a given pixel in an image. You are given an image represented by an m x n grid of integers, where the image[i] represents the pixel value at position (i, j). You are also given the coordinates of a starting pixel (x, y) and a new colour to use for the flood fill operation.

Applications of Stack Data Structure in Programming

The key idea behind using a stack is that it allows for easy access to the most recently added element and easy removal of that element, which can be useful in situations where you need to keep track of a history of actions or reverse actions. So based on various use cases, there are several applications of the stack in coding problem-solving and computer programming.

Stack Data Structure Operations and Implementation

The stack data structure is a type of collection that follows the Last In, First Out (LIFO) principle, meaning that the last item added to the stack will be the first one to be removed.Stack is a linear data structure that supports two primary operations: push and pop. When we add an element to the top, it is called a push operation. When we remove an element from the top, it is called a pop operation.

Implement Stack using Queues

Write a program to implement a stack using queues. We must use queue operations like enqueue, dequeue, front, size to implement stack operations like push, pop, and top. We have discussed three approaches: 1) Using two queues: O(n) pop and O(1) push 2) Using two queues: O(1) pop and O(n) push 3) Using one queue: O(1) pop and O(n) push.

Implement Queue Using Stacks

Write a program to implement queue using stack. We should use stack operations like push, pop, top, size, and isEmpty for implementing queue operations like enqueue, dequeue, and front. In this blog, we have discussed two approaches for implementing queue using two stacks: 1) Dequeue O(1) and Enqueue O(n) 2) Enqueue O(1) and Dequeue O(1).

Sort a Stack

Given a stack, write a program to sort a stack in ascending order. We are not allowed to make assumptions about how the stack is implemented. The only functions to be used are push(s, x), pop(s), top(s), isEmpty(s). In this blog, we have discussed two approaches: 1) Sorting stack using temporary stack 2) Sorting stack using recursion.

Find Next Greater Element

Given an array, find next greater element for every element in array (NGE). The next greatest for an element is the first largest element on the right side. Elements for which no next largest element exists, consider the next greater element as -1. Note: We have discussed two stack based solutions: 1) Traversing from left to right 2) Traversing from right to left.

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1. Write a program to compute how much water it can trap after raining. This is a famous interview problem to learn time and space complexity optimization using various approaches. Two pointers approach provides an efficient solution using O(n) time and O(1) space.

Iterative Preorder, Inorder and Postorder Traversal using Stack

In recursive dfs traversals (preorder, inorder and postorder), output depends on the order in which we process the root node. Algorithm is simple and easy to visualize! The critical question is: How do we implement these traversals without using recursion? The answer is: We use stack to simulate a recursive dfs traversal into an iterative dfs traversal.

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.