CODEWITHSUNDEEP
c++arraysdata-structurestime-complexity
markus
markus

Reputation: 25

sum of complexity

assume you are given

A=[2, 5, 7, 2, 6, 7, 6, 5, 6, 5].  

Sum=[0, 0, 0, 12, 0, 8, 7, 28, 5, 6].

use O(n) extra space and **must run in O(n) time****.

Upvotes: 0

Views: 74

Answers (1)

Jarod42
Jarod42

Reputation: 217135

If you are allowed to use std::unordered_map, you might use something like:

auto IntervalSum(const std::vector<int>& A)
{
    std::vector<int> res;
    std::unordered_map<int, int> m;
    int sum = 0;

    for (auto e : A) {
        sum += e;
        if (auto [it, inserted] = m.emplace(e, sum); !inserted) {
            res.push_back(sum - e - it->second);
            it->second = sum;
        } else {
            res.push_back(0);
        }
    }
    return res;
}

Demo

The C++17 construct

if (auto [it, inserted] = m.emplace(e, sum); !inserted) {

might be rewritten in previous version (C++11/C++14):

auto p = m.emplace(e, sum);
auto it = p.first;
bool inserted = p.second;
if (!inserted) {

Upvotes: 1

Related Questions