The Algorithm Design Manual (3rd) Exercise Solution 'E3-24'

Table of Contents

Introduction
Repository
Exercise 3-24
- Question
- Solution

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-24

Question

An array A is called k-unique if it does not contain a pair of duplicate elements within k positions of each other, that is, there is no i and j such that $A[i] = A[j]$ and $|j − i| ≤ k$ . Design a worst-case $O(n log k)$ algorithm to test if A is k-unique.

Solution

First, set a new binary tree

Second, insert a element of v into the tree one by one target elements are in the range of index[0, k] if the tree already has the incomming value, return false.
time complexity: $O(klogk)$

Third, for each the rest of elemens in the range of index[k+1,n), (lets say the index of the element is i) remove the value of the element v[i-k-1] and insert the i's element into the tree.
If the tree already has the incomming value, return false.
time complexity: $O((n-k)logk)$

Total time complexity: $O(nlogk)$

Below is C++ code.

#include <cassert>
#include <concepts>
#include <iostream>
#include <set>
#include <stdexcept>
#include <vector>

template <std::totally_ordered T>
bool check_k_unique(const std::vector<T>& v, size_t k) {
    if (v.size() <= k) throw std::invalid_argument("invalid k");

    // first, set a new binary tree

    // second, insert a element of v into the tree one by one
    //  target elements are in the range of index[0, k]
    //  if the tree already has the incomming value, return false
    //  time complexity: O(klogk)

    // third, for each the rest of elemens in the range of index[k+1,n),
    //  (lets say the index of the element is i)
    //  remove the value of the element v[i-k-1] and
    //  insert the i's element into the tree
    //  if the tree already has the incomming value, return false
    //  time complexity: O((n-k)logk)

    // total time complexity: O(nlogk)

    std::set<T> tree{};
    for (size_t i{0}; i <= k; i++) {
        const auto [it, is_inserted]{tree.insert(v[i])};
        if (!is_inserted) return false;
    }

    for (size_t i{k + 1}; i < v.size(); i++) {
        tree.erase(v[i - k - 1]);
        const auto [it, is_inserted]{tree.insert(v[i])};
        if (!is_inserted) return false;
    }

    return true;
}

int main(int argc, char const* argv[]) {
    assert(!check_k_unique<int>({1, 1}, 1));
    assert(check_k_unique<int>({1, 2}, 1));
    assert(check_k_unique<int>({1, 2, 1}, 1));
    assert(!check_k_unique<int>({1, 2, 1}, 2));

    std::vector<int> v{4, 1, 2, 6, 5, 3, 4, 1, 2, 6, 5, 3};
    assert(check_k_unique(v, 1));
    assert(check_k_unique(v, 2));
    assert(check_k_unique(v, 3));
    assert(check_k_unique(v, 4));
    assert(check_k_unique(v, 5));
    assert(!check_k_unique(v, 6));
    assert(!check_k_unique(v, 7));
    assert(!check_k_unique(v, 8));
    assert(!check_k_unique(v, 9));
    assert(!check_k_unique(v, 10));
    assert(!check_k_unique(v, 11));

    return 0;
}