Problem: Statement Write a function to count number of distinct elements given in a sorted array.
Difficulty level: Easy
Test Cases
 [2, 2, 3, 3, 4, 5] > 4
 [4, 5, 7, 10, 15] > 5
 [1, 1, 1, 2, 5, 5, 5] > 3
 [1, 2, 3, 4, 4, 5, 5, 5] > 5
 None > 0
Algorithm

Python Set Solution
 Add elements of array to set and return it's length.

Dictionary Solution
 Iterate through the given array
 If element was previously not seen in dictionary than,
 Add the element to dictionary with value of 1.
 Return the length of dictionary.

Best Solution
 Initialise index at 1
 Iterate from 1 to length of given array.
 If, the element at current iteration i is not equal to element at position of index  1, than
 Overwrite the element at index with the element at current iteration i
 increment value of index by 1
 Return index
Time and Space complexity
 Time complexity of all solutions: O(n)

Space complexity
 Set: O(n)
 Dictionary: O(n)
 Best solution: O(1)
Code
class ValidElements(object):
def validElements(self, arr):
if not arr:
return 0
return len(set(arr))
def validElements2(self, arr):
if not arr:
return 0
seen = {}
for entry in arr:
if entry not in seen:
seen[entry] = 1
return len(seen)
def validElements3(self, arr):
if not arr:
return 0
index = 1
for i in range(1, len(arr)):
if arr[index  1] != arr[i]:
arr[index] = arr[i]
index += 1
print(arr)
return index
Unit Test
import unittest
from validElements import ValidElements
class TestValidElements(unittest.TestCase):
def testValidElements(self, func):
self.assertEqual(func([2, 2, 3, 3, 4, 5]), 4)
self.assertEqual(func([1, 2, 3, 4, 4, 5, 5, 5]), 5)
self.assertEqual(func([1, 1, 1, 2, 5, 5, 5]), 3)
print("All test cases passed")
def main():
test = TestValidElements()
elements = ValidElements()
test.testValidElements(elements.validElements)
test.testValidElements(elements.validElements2)
test.testValidElements(elements.validElements3)
if __name__ == "__main__":
main()
Original article
Github solution
Top comments (0)