Skip to main content

· 2 min read
Sarthak Mohanty
  • A subarray is a contiguous part of array and maintains relative ordering of elements. For an array/string of size n, there are n*(n+1)/2 non-empty subarrays/substrings.
  • A subsequence maintain relative ordering of elements but MAY or MAY NOT be a contiguous part of an array. For a sequence of size n, we can have 2^n-1 non-empty sub-sequences in total.
  • A subset MAY NOT maintain relative ordering of elements and can or cannot be a contiguous part of an array. For a set of size n, we can have (2^n) sub-sets in total.
caution

  • Every Subarray is a Subsequence.

  • Every Subsequence is a Subset.

  • ehen we find subset of a set we dont take a subset which is a premutation

    • example {1,2,3}:
      • {2,1} and {1,2} are the same thing that is {2,1} is permutation of {1,2} , so we count it only once

To add to this there is usually a confusion with substrings. A substring is exactly the same thing as a subarray but in the context of strings.

Consider an array: array = [1,2,3,4]

  • Subarray : [1,2],[1,2,3] - is continous and maintains relative order of elements
  • Subsequence: [1,2,4] - is not continous but maintains relative order of elements
  • Subset: [1,3,2] - is not continous and does not maintain relative order of elements. All its permutations are also valid but only one set of these permulations can be counted once.

· 10 min read
Sarthak Mohanty
tip

Reference:~

caution

LinkedList is faster than ArrayList while inserting and deleting elements, but it is slow while fetching each element.

  • LinkedList is faster in add and remove compared to ArrayList. ArrayList is faster in get().

Elements to be added or removed are too large, go for LinkedList. Usage of get() is more, go for ArrayList. Again, if you don’t have element access in a large number, go for LinkedList.