Tyson's blog

What is a priority queue?It is essentially a heap disguised as a queue, as the priority queue interface only allows elements to be removed from the front and added at the back, making it appear like a queue. Additionally, the elements within a priority queue are automatically arranged according to their priority. How is this ordering achieved? By default, priority_queue uses a max-heap to sort elements. This max-heap is represented as a complete binary tree using a vector. What is a Heap?A heap ...

QuestionLeetCode Link | 347. Top K Frequent Elements | Medium Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size. Constrains 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 k is in the range [1, the number of unique elements in the array]. It is guaranteed that the answer is unique. ExamplesExample 1 Input: ...

QuestionLeetCode Link | 239. Sliding Window Maximum | Hard You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. (The max value in that window) Constrains 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 1 <= k <= nums.length ExamplesExample 1 Input: nums ...

What is a Deque?Deque (Double-Ended Queue): Definition: A deque is a data structure that allows insertion and deletion of elements from both ends: the front (head) and the back (tail). Operations: pushBack(x): Add element x to the back. pushFront(x): Add element x to the front. popBack(): Remove and return the element from the back. popFront(): Remove and return the element from the front. Advantages: Provides O(1) time complexity for both append and pop operations from either end. Flexible f ...

QuestionLeetCode Link | 150. Evaluate Reverse Polish Notation | Medium You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation. Evaluate the expression. Return an integer that represents the value of the expression. Note that: The valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. The division between two integers always truncates toward zero. There will not be a ...

QuestionLeetCode Link | 1047. Remove All Adjacent Duplicates In String | Easy You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them. We repeatedly make duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique. Constrains 1 <= s.length <= 10^5 s consists of lowercase English letters. ...

QuestionLeetCode Link | 20. Valid Parentheses | Easy Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type. Constrains 1 <= s.length <= 10^4 s consists of par ...

QuestionLeetCode Link | 225. Implement Stack using Queues | Easy Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty). Implement the MyStack class: void push(int x) Pushes element x to the top of the stack. int pop() Removes the element on the top of the stack and returns it. int top() Returns the element on the top of the stack. boolean empty() Returns true if the stack is empty, f ...

QuestionLeetCode Link | 232. Implement Queue using Stacks | Easy Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Implement the MyQueue class: void push(int x) Pushes element x to the back of the queue. int pop() Removes the element from the front of the queue and returns it. int peek() Returns the element at the front of the queue. boolean empty() Returns true if the queue i ...

QuestionLeetCode Link | 459. Repeated Substring Pattern | Easy Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. Constrains 1 <= s.length <= 10^4 s consists of lowercase English letters. ExamplesExample 1 Input: s = “abab”Output: trueExplanation: It is the substring “ab” twice. Example 2 Input: s = “aba”Output: false Example 3 Input: s = “abcabcabcabc”Output: trueExplanation: It is the sub ...