Freaks City

Linear dynamic programming problems, such as knapsack variations, typically process states in a strict sequential order—either forward or backward. Each state depends strictly on previously computed states. Interval dynamic programming breaks this sequential dependency. In many scenarios, the order of combining or splitting elements is not fixe ...

Splay tree is a self-adjusting binary search tree introduced by Daniel Sleator and Robert Tarjan. Unlike Treap which assigns random priorities to nodes, Splay tree performs rotations to move accessed nodes to the root, thereby maintaining balance during operations. Core Operations Node Clearing Reset all fields of a node to zero: void clear(int ...

The solution involves verifying that the array length equals the maximum value plus one, then sorting the array and confirmnig that elements form a sequence from 0 to max - 1. class Solution { public: bool isGood(vector<int>& nums) { int maxVal = 0; for(auto val : nums){ maxVal = max(maxVal, val); ...

LeetCode 704. Binary Search Problem Link: 704. Binary Search Binary Search (Left-Closed Right-Closed) Implementation class Solution { public: int search(vector<int>& numbers, int value) { int left = 0, right = numbers.size() - 1; while (left <= right) { int middle = (left + right) / 2; if (num ...

Level Order Traversal Appraoch Key steps for inversion using level order traversal: Enqueue the root node Swap left and right chidlren of the dequeued node Enqueue non-null children for further processing void invertViaLevelOrder(Node* root) { if (!root) return; queue<Node*> q; q.push(root); while (!q.empty()) ...

The "Hanging Line" (or "Suspension Line") method is an efficient technique for identifying the largest rectangular area within a histogram or a grid of binary values. It optimizes the naive brute-force approach from O(N²) to O(N) complexity. Core Concept Consider a histogram of bars with varying heights. For any bar at index ...

Dynamic programming solves problems by combining optimal substructures. For the coin change problem, we need to find the minimum number of coins to make up a given amount. Approach 1: Coin Selection as Subproblem Create a 2D table where rows reprseent available coins and columns represent target amounts. Each cell dp[i][j] stores the minimum co ...

Bulb Switcher III There are n bulbs arranged in a line, numbered from 1 to n from left to right. Initially, all bulb are turned off. At time k (where k ranges from 0 to n-1), we turn on the bulb at position light[k]. A bulb turns blue when both conditions are met: The bulb is currently on All bulbs to its left are also on Return the number of ...

Determining the nearest upcoming Chinese solar term requires mapping a given Gregorian month and day to a fixed chronological sequence. The operational cycle spans from early February of one year through late January of the subsequent year, with dates on or after February 4 assigned to the primary cycle and earlier dates mapping to the followin ...

Problem Description A monarch rewards a loyal knight with gold coins based on a unique progressive payment system. The scheme is as follows: On the first day, the knight receives 1 gold coin. For the subsequent two days (Day 2 and Day 3), the knight receives 2 gold coins per day. Following that, for the next three days (Day 4, Day 5, and Day 6 ...