3 posts tagged with "day-1"

Let's increase problem level further.

Problem​

Given a grid of integers L = [[A_1,1, A_1,2, A_1,3, ..., A_1,M], [A_2,1, A_2,1, A_2,3, ..., A_2,M], [A_3,1, A_3,2, A_3,3, ..., A_3,M], [..., ..., ..., ..., ...], [A_N,1, A_N,2, A_N,3, ..., A_N,M]]. Where A_i,j ≥ 0, 0 ≤ i ≤ N, 0 ≤ j ≤ M. You have to find the least perimeter of rectangle which adds up to a given integer K.

So, What if the numbers can also be negative?

We can't use sliding window algorithm then. First we will compute prefix sum and then sort it with their respective index (sort them as {prefixL[i],i}). Then we will apply binary search on it for every index i to look for an element whose index j is greater than index i and whose value is equal to prefixL[i] + K. This will take $\cal{O}(n \cdot \log(n))$ time.

Let us start with a problem

Problem​

Given a list of integers L = [A₁, A₂, A₃, …, A_N]. Where A_i ≥ 0, 0 ≤ i ≤ N. You have to find the shortest contiguous segment in the list which adds up to a given integer K. If there are more than one such segment, print one of them.