Daily DSA and System Design Journal – 16

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

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

DSA System Design Analogy

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