Daily DSA and System Design Journal - 16

🔥 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

1. Sort the array in ascending order.
2. Initialize a variable prev = -inf to represent the last assigned value.
3. 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 set prev = 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):

1. The CDN checks if it already has a cached copy.
2. If not, it pulls it from your origin server.
3. 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. 🚀