10
$\begingroup$

What is a contiguous subarray? I have tried searching online and have found pages about solving the largest contiguous subarray problem but none with a definition or explanation of what contiguous in this actually is.

Ex: Wikipedia: Maximm subarray problem has no explanation of why the given "subarray" is contiguous or what contiguous means in the context.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I believe it's just a contiguous (in order) subset of the set. The Wikipedia page you referenced, in the first paragraph gives an example: "For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6." $\endgroup$
    – Jared
    Jun 6, 2015 at 4:52
  • $\begingroup$ Nicely explained with program: javabypatel.blogspot.in/2015/08/… $\endgroup$
    – Jayesh
    Oct 23, 2015 at 11:25

2 Answers 2

Reset to default
9
$\begingroup$

This is just the ordinary dictionary definition of "contiguous": all adjacent in space. A subarray is defined by any subset of the indices of the original array; a contiguous subarray is defined by an interval of the indices: a first and last element and everything between them.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ This answer is misleading in the sense that a subarray, in most articles/books/videos/programming languages/situations, means a contiguous slice of the original array. Sometimes people write contiguous subarray for the sake of extra clarity, which is a bad practice. If one want to be clearer, write contiguous subsequence instead. All respectable definitions of a subarray that I can remember require the indices selected be contiguous. On the other hand, a subsequence is (overwhelmingly if not always) defined without that requirement. $\endgroup$
    – John L.
    Feb 17, 2021 at 16:44
  • 2
    $\begingroup$ I agree with John, a subarray is an array, i.e. implicitly contiguous. For a non-contiguous selection of elements, you might say subset if order need not be preserved and subsequence if it does. $\endgroup$
    – Yves Daoust
    Mar 8, 2022 at 8:41
-1
$\begingroup$

EDIT: I get want people are saying. The actual definition of contiguous subarray is any sub series of elements in a given array that are contiguous ie their indices are continuous.

So given [1,2,3,4,5,6]:

[1,2,3], [3,4], [3,4,5,6] are all valid contiguous subarrays. Any algorithm can be used to generate the subarrays.

Personal note: What was confusing for me was most explanations either use or reference a specific problem or condition set to generate the subarrays. Most don't specifically state there's no direct relationship between the problem and the definition of contiguous subarrays.

For me it's the same as asking:

Q: "What does + do?"

A: "4+4=8"

Me: "OK, so I can only use + with 4, got it."

This is how my brain worked to grok the definition, so hopefully it helps someone else out.

ORIGIONAL ANSWER:

OK from what I've worked out the term "contiguous subarray" is a misnomer.

Subarray = "any part or section of an array" Contiguous = "data that is moved or stored in a solid uninterrupted block."

But AFAIK "Contiguous" still needs to be qualified by further conditions.

For example this Facebook/Meta test question:

Contiguous Subarrays

You are given an array a of N integers. For each index i, you are required to determine the number of contiguous subarrays that fulfills the following conditions:

The value at index i must be the maximum element in the contiguous subarrays, and These contiguous subarrays must either start from or end on index i.

Or this LeetCode Example:

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

So just asking for "contiguous subarray" without the conditions of what makes a subarrary contiguous is invalid.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ No additional qualifications are needed; it is perfectly fine to refer to a "contiguous subarray" without any further conditions. I don't understand what additional qualifications you think are needed when using the phrase "contiguous", or why you think that. Your examples don't demonstrate that additional qualifications are needed. "what makes a subarray contiguous" makes no sense to me. $\endgroup$
    – D.W. ♦
    Mar 8, 2022 at 6:43
  • $\begingroup$ So for both the problems above, if I just gave you an array and literally just said "Find the contiguous subarray(s)" without any conditions would you be able to solve it? I guess my point isn't about the definition of "contiguous subarray" and more that people on the internet tend to use that term as a catch all, often inferring conditions without explicitly stating them. $\endgroup$
    – Geordie
    Mar 8, 2022 at 7:53
  • $\begingroup$ "I don't understand what additional qualifications you think are needed when using the phrase "contiguous", or why you think that.": "contiguous" could mean "all the elements of the same color" or "all elements higher than the current element but only of lower index"... $\endgroup$
    – Geordie
    Mar 8, 2022 at 8:09
  • $\begingroup$ I realize the exact definition of "contiguous" doesn't need qualification, but when the term "contiguous subarray" is used in the context of a problem, it means some rules must be applied to the original array to generate the subarrays. Most questions of Stack Overflow etc aren't asking: "what's a contiguous subarray?", they're asking: "what's a contiguous subarray as applied to a specific problem with specific conditions?" Now if you don't know that and think contiguous subarray has some inherent algorithmic value it get's confusing. $\endgroup$
    – Geordie
    Mar 8, 2022 at 8:10
  • 2
    $\begingroup$ You try to force a meaning that does not exist. Taking another examples, a "diagonal dominant square matrix" is square, regardless the extra property of being diagonal dominant. I don't think that the OP is focusing on a specific case, be it the maximum subarray problem. $\endgroup$
    – Yves Daoust
    Mar 8, 2022 at 8:45

Your Answer

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

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