This question was asked in a technical interview, I am looking for some feedback on my solution.

Given a list of integers and a number K, return which contiguous elements of the list sum to K. For example, if the list is [1, 2, 3, 4, 5] and K is 9, then it should return [2, 3, 4].

The Ask

My solution works with my test cases, but I would like feedback on how others would approach the problem and where my code could be altered to improve efficiency and runtime. Currently, I have a nested for loop and I believe my solution is O(n2).


def contigSum(nums, k):

    for i, num in enumerate(nums): 
        accum = 0
        result = [] 
        # print(f'Current index = {i}')
        # print(f'Starting value = {num}')

        for val in nums[i:len(nums)]:
            # print(f'accum = {accum}')
            # print(f'accum = {accum} + {val}')
            accum += val 

            if accum == k: 
                print(f'{result} = {k}')
                return 0
            # else:
                # print(f'accum = {accum}')

    print('No match found')
    return 1

Test Cases

nums0 = []
k0 = None 
contigSum(nums0, k0)

nums6 = [1, 2, 3]
k6 = 99
contigSum(nums6, k6)

nums1 = [1, 2, 3, 4, 5]
k1 = 9
contigSum(nums1, k1)

nums2 = [-1, -2, -3]
k2 = -6
contigSum(nums2, k2)

nums4 = [5, 2, 6, 11, 284, -25, -2, 11]
k4 = 9 
contigSum(nums4, k4)

nums5 = [10, 9, 7, 6, 5, 4, 3, 2 ,1]
k5 = 20 
contigSum(nums5, k5)
  • 1
    \$\begingroup\$ Why is Lyft part of your title as it's mentioned nowhere in the question? Also, why isn't [4,5] a valid answer if K is 9? \$\endgroup\$
    – IEatBagels
    Commented Nov 15, 2018 at 21:44
  • 1
    \$\begingroup\$ The question was asked by Lyft in a technical interview - I agree, it is not relevant to the question. I'll remove it. [4, 5] is a valid solution, but I wrote my solution to stop at the first successful match. \$\endgroup\$
    – Phaedrus
    Commented Nov 15, 2018 at 21:46
  • 1
    \$\begingroup\$ I believe that specifying it is a technical interview might be useful to the question though (In my opinion) as it may orient the review in another way :) \$\endgroup\$
    – IEatBagels
    Commented Nov 15, 2018 at 21:49
  • 1
    \$\begingroup\$ The inclusion of negative integers makes it impossible, I think, to get a linear solution, unfortunately... \$\endgroup\$
    – Graipher
    Commented Nov 16, 2018 at 12:33
  • 2
    \$\begingroup\$ Also, if you include test cases, you should include the expected outcome as well. \$\endgroup\$
    – Graipher
    Commented Nov 16, 2018 at 12:34

1 Answer 1


Unused code

for i, num in enumerate(nums):, the i variable is used in your commented code, but commented code shouldn't exist, so i shouldn't exist either.

To come back on the commented code, I hope you didn't submit your solution with these comments as this is a (in my opinion) very bad practice. What does commented code mean after all? These comments could all be replaced by any debugging tool.

Running time

I believe your solution is actually running on \$O(n*\log(n))\$ time as the nested loop doesn't restart at index 1 every time it runs (which is a good thing). Seems like this is wrong.

Code structure

Usually, in an interview question code structure is pretty important. Right now you have one method that does everything. You should at least have a method that returns your result and one that prints it. Something like :

def main():
    nums = ...
    k = ...
    print(contigSum(nums, k))

def contigSum(nums, k):

and contigSum should return the result, not print it.

  • \$\begingroup\$ Excellent, thank you for pointing these out - much appreciated. \$\endgroup\$
    – Phaedrus
    Commented Nov 15, 2018 at 22:16
  • 5
    \$\begingroup\$ Even though the nested loop doesn't restart at index 1 every time this one is still \$O(n^2)\$. Please double-check your reasoning. \$\endgroup\$
    – vnp
    Commented Nov 15, 2018 at 23:05
  • \$\begingroup\$ @vnp You're right, I'm still struggling a little bit with the Big O notation. \$\endgroup\$
    – IEatBagels
    Commented Nov 20, 2018 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.