Hi, folks! Today I solved three problems on LeetCode : Sliding window maximum, Implement queue with stack and Perfect squares.
These problems are great for improving our logical thinking skills. Let me walk you through the logics for each problem.
The first problem Sliding window maximum. The problem states that we are provided with a numbers array and a window of size k. We can only see k elements from the window. The window will start sliding from first element to last element of array according to window size. For every window slide, we have to return the maximum number.
We can solve this problem in two ways based on my understandings. The first approach is using nested for loop: one for loop to traverse through the array and the other for loop is to keep track of k elements and we will use max to find the maximum number in that k elements and then we create a list with all the maximum numbers, and return that list.
The second approach is using dequeue. Dequeue can handle push, pop and top operations in the both ends(first and last). We will use dequeue to store the indices of maximum number for every k(size of window) in array. Whenever the window size exceeds then we will pop a specific index from dequeue. In this way we will return all the maximum numbers in a list.
The second problem Implement queue with stack. In this problem we can use two stacks to achieve the functionality of queue. lets say we have stack one and stack two. Whenever there is push operation we can push it to stack one. For pop and top operations, we check whether stack two is empty. If it is, we will shift all the elements from stack one to stack two Otherwise we directly apply pop or top operations on stack two. In this way we can implement the queue with help of two stacks.
The third problem Perfect squares. In this problem, we are given an input number, and we need to find the minimum number of perfect squares are required to sum up to that input number. We can solve this problem by initializing two arrays. One array is to store all the perfect squares less than input number, and the other is used to keep track of minimum number of perfect squares that sum up to give input number. This way can efficiently solve the problem.
I hope my experience will be useful.
Top comments (0)