## DEV Community

CodeWithML

Posted on • Updated on

# Valid Elements in a sorted array

### Problem: Statement Write a function to count number of distinct elements given in a sorted array.

#### 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()
``````