Leipzig Gophers
blog

🔗Virtual Meetup #27 wrap-up

Algorithm Challenge

Meetup #27 took place on 2022-05-10 19:00 CEST and was virtual again and we had an interesting problem-solving live-coding challenge.

Slides and code: gitlab.com/telo_tade/prefix_suffix_arrays

Problem

You are given a list of numbers. Find its longest slice that sums to zero.

First, clarify:

We collaboratively went from a naive O(n^3) solution to a slightly improved O(n^2) one using an auxiliary data structure: a prefix sum array.

Takeaways:

The key insight may become obvious in an example:

input:      [1, 2, 3,  4, -3, -1,  9]
prefix sum: [1, 3, 6, 10,  7,  6, 15]

Two elements in the prefix array that have the same value (e.g. 6) allow us to determine a subsequence that sums to zero.

A final pass through the prefix sum array allows to keep track of repeated numbers and find the longest sequence. If you iterate throught the prefix sum array from front and back simultaneously, you can stop at the first occurence (same time complexity, still).

We implemented a version that defined a type set for numbers; similar to the ones found in golang.org/x/exp/constraints.

In this case, a non-generic version may use reflection and be slower and more inconvenient to write.

Find out more at: gitlab.com/telo_tade/prefix_suffix_arrays; we enjoyed the interactive format. If that’s something for you too, check out Hamburg Whiteboard Coders meetup.


Join our meetup to get notified of upcoming events!