This content originally appeared on DEV Community and was authored by I.K
🔥 Day 16 — Greedy Growth & Global Pulls 🌍⚙️
Greedy algorithms and CDNs both thrive on balance — optimizing decisions locally to maximize global efficiency. Today’s combo: maximizing distinctness in arrays and minimizing latency with pull-based caching.
🧩 DSA Problems [1 hr]
Problem: 3176. Find Maximum Distinct Elements After Operations (the problem you described matches this one)
đź’ˇ Approach: Greedy
🧠Intuition
We want to maximize the number of distinct elements in an array after at most one operation per element,
where each element nums[i] can be changed by any value in the range [nums[i] - k, nums[i] + k].
Key idea:
- After applying all operations, all numbers lie within
[min(nums) - k, max(nums) + k]. - To make as many unique numbers as possible, we should assign the smallest valid unused value to each number.
🪜 Step-by-Step Greedy Process
- Sort the array in ascending order.
- Initialize a variable
prev = -infto represent the last assigned value. - For each number in sorted order:
- Its valid range after operations is
[num - k, num + k]. -
Choose the smallest possible value that’s still greater than
prev:
curr = min(max(num - k, prev + 1), num + k) If
curr > prev, increment the count and setprev = curr.
This ensures that every element takes the earliest distinct spot available.
đź’» Code Implementation
import math
class Solution:
def maxDistinctElements(self, nums: List[int], k: int) -> int:
nums.sort()
cnt = 0
prev = -math.inf
for num in nums:
curr = min(max(num - k, prev + 1), num + k)
if curr > prev:
cnt += 1
prev = curr
return cnt
⚙️ Complexity
| Measure | Complexity |
|---|---|
| ⏱ Time | O(n log n) — due to sorting |
| 💾 Space | O(log n) — typical for in-place sorting |
🧠Insights
- This greedy algorithm ensures local optimality per element, leading to global optimal distinctness.
- It parallels interval scheduling — minimizing conflicts while maximizing utilization.
- Alternative view: we’re assigning each element a unique “slot” within its valid range.
🌍 SYSTEM DESIGN — Roadmap.sh [1 hr]
🧠Pull CDNs
Pull CDNs automatically fetch and cache your content on demand — that is, only when users request it for the first time.
When a user requests content (like an image or CSS file):
- The CDN checks if it already has a cached copy.
- If not, it pulls it from your origin server.
- The content is cached and served to future users until it expires (based on TTL).
⚙️ How It Works
- Clients access resources via CDN URLs (e.g.,
cdn.example.com/images/logo.png). - The CDN routes the request to the nearest edge node.
- If the content is cached and valid, it’s served instantly.
- Otherwise, it’s fetched from the origin, cached, and then served.
đź•“ TTL (Time To Live)
- Determines how long cached content remains before it’s revalidated or re-fetched.
- Choosing a good TTL balances freshness (short TTL) vs. efficiency (long TTL).
âś… Pros
- Hands-off caching — no need to push content manually.
- Great for dynamic or frequently accessed resources.
- Balances load across global edge servers.
⚠️ Cons
- First request latency — the initial user experiences a delay while the content is fetched.
- Redundant traffic — if TTLs expire too soon, the same files may be re-fetched repeatedly.
- Possible staleness — if content changes faster than cache invalidation.
đź’ˇ Ideal Use Cases
| Use Case | Reason |
|---|---|
| High-traffic websites | Frequent access keeps caches warm |
| APIs serving static responses | Edge caching reduces origin hits |
| Video or image-heavy apps | Large content benefits from proximity caching |
🧩 DSA ↔ System Design Analogy
| DSA Concept | CDN Concept |
|---|---|
| Assigning smallest valid distinct value | Fetching content lazily, only when needed |
| Greedy range compression | Cache-space optimization |
Avoiding duplicates via prev tracking |
Avoiding redundant pulls via TTL |
Both operate on lazy evaluation principles — do the minimal necessary now to maximize global efficiency later. ⚙️
âś… Day 16 Summary
Greediness isn’t always bad — when used smartly, it leads to global harmony. Whether assigning numbers or caching content, optimal local choices build global distinctness and efficiency. 🚀
This content originally appeared on DEV Community and was authored by I.K
I.K | Sciencx (2025-11-01T17:07:50+00:00) Daily DSA and System Design Journal – 16. Retrieved from https://www.scien.cx/2025/11/01/daily-dsa-and-system-design-journal-16/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.