Teaching Kids Programming – Count of Sublists with Same First and Last Values

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums, return the number of sublists where the first element and the last element have the same value.

Constraints
n ≤ 10,000 where n is length of nums
Example 1
Input
nums = [1, 5, 3, 1]
Output
5
Explanation
The sublists with same first and last element are: [1], [5], [3], [1], [1, 5, 3, 1].

Hints:
Try to store how many occurrences of the current integer (inclusive) has already been encountered.

Count SubLists with Same First and Last Value via Bruteforce Algorithm

We bruteforce the sublists in O(N^2) time and increment the answer if the first and last value is the same:

1
2
3
4
5
6
7
8
9

class Solution:
    def countSubLists(self, nums):
        ans = 0
        n = len(nums)
        for i in range(n):
            for j in range(i, n):
                if nums[i] == nums[j]:
                    ans += 1
        return ans

class Solution:
    def countSubLists(self, nums):
        ans = 0
        n = len(nums)
        for i in range(n):
            for j in range(i, n):
                if nums[i] == nums[j]:
                    ans += 1
        return ans

Count SubLists with Same First and Last Value via Hash Map

We can keep tracking of the numbers we have seen and how many time they appear. For example, if a number has appeared three times so far (including curren digit), then there should be 3 sublists which should be counted to final answer.

Time and space complexity is O(N):

1
2
3
4
5
6
7
8

class Solution:
    def countSubLists(self, nums):
        ans = 0
        seen = defaultdict(int)
        for i in nums:
            seen[i] += 1
            ans += seen[i]
        return ans

class Solution:
    def countSubLists(self, nums):
        ans = 0
        seen = defaultdict(int)
        for i in nums:
            seen[i] += 1
            ans += seen[i]
        return ans

–EOF (The Ultimate Computing & Technology Blog) —