DEV Community: Abubakar Sadiq Ismail

3Sum Closest

Abubakar Sadiq Ismail — Sun, 09 Oct 2022 16:07:52 +0000

Problem 3 Closest Sum
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

The idea that a lot of people will think of is to brute force all the possible 3 combinations of integers in the nums array sum them and return the closest one.
This solution works but comes with a cost which is the high time complexity of O(n^3)

There is a better way to do it, yes there is.
Using the two pointer technique.
Read about two pointer technique

First Sort the array of nums.
the time complexity of the sorting nums is nlog(n)

declare the maxSum = 0

Then loop through the array from 0 to n-2.

Declare the two pointers
l = i + 1
r = n -1
loop while l < r
calculate the sum as nums[i] + nums[l] + nums[r]

check if i = 0 sum > 0;
reassign maxSum = sum

check if sum == target
if yes return sum

check if sum is closer than previous sum;
if sum > 0
check if target-sum < target-maxSum
if yes maxSum = sum
else sum < 0
target-sum > target -maxSum
maxSum = sum

Next is to move the pointer

if sum < target
increment l pointer

if sum > target
decrement r counter

and hence you don't have to bother about missing the values because the array is sorted.
nums[r] pointer is the max value hence you decrease r pointer to reduce the sum, and check again.

else if sum is less than target nums[l] pointer is the smallest and hence you increment the counter value, l=l+1, nums[l+1] which is larger than nums[l] hence you decrease in other to check for l+1.
until l == r.
Then you increment break out inner loop and continue to the first loop by incrementing i.
set l to i+1
set r to n-1.
Repeat the process
And when you get to i = n-2. Repeat the process stop and
Return MaxSum.
Given the time complexity as nlog(n) + O(n^2).
We take the max And the overall time complexity is O(n^2)
with O(1) space complexity.

Find the element that appear once in array

Abubakar Sadiq Ismail — Tue, 04 Oct 2022 15:00:52 +0000

Problem
Given an array with items.
each item in the array appear twice except once element.
E.g [1,4,3,4,1]
here the element 3 appear only once hence it should be returned.
Solution
Prerequisite knowledge hashMap or Dictionary.
How do you find the element.
Using Dictionary.

1 Create a Dictionary.
2 Assign the key of the dictionary as the array items, and the value as count of times it appears in the array.
3 Return the dictionary item with the value of 1.

Create items dictionary
Loop through the array i = 0,....n = length of the array-1.
If the array[i] is not a key in the items dictionary create a key with value of 1
if the array[i] is a key in the dictionary increment the value by 1.

Loop through the dictionary of items to get the key with 1 as value and return it, if all are more than one.

return -1.

Time Complexity O(n)
Because we are looping through the array n times.
Space Complexity O(n)
Because we are creating a map with at worst case n keys.

Linear Search

Abubakar Sadiq Ismail — Mon, 03 Oct 2022 22:05:40 +0000

Linear search algorithm.

Given an array of items.
You want to find the given index of an element.
The linear search algorithm returns the index of the element, or -1 if the element is not found.

Linear search works by going through the array from index 0,....n-1
comparing array[index] to element.
If they match you return the index.

if the array elements are compared from index 0 to n-1 and no element matches the element.
you return -1.

Hence the pseudo code
Loop through array from index = 0, to n-1.
if array[index] = element
return index

return - 1

Time Complexity is O(n).
because we are looping through the array n times.
Space Complexity is O(1).
We are not creating any new variable and hence using constant space complexity

Day 10 I4G10DaysofCodeChallenge

Abubakar Sadiq Ismail — Fri, 30 Sep 2022 20:05:29 +0000

Day 10.
Final day,
A valid number can be split up into these components (in order):

A decimal number or an integer.
(Optional) An 'e' or 'E', followed by an integer.
A decimal number can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One of the following formats:
One or more digits, followed by a dot '.'.
One or more digits, followed by a dot '.', followed by one or more digits.
A dot '.', followed by one or more digits.
An integer can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One or more digits.
For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].

Given a string s, return true if s is a valid number

This problem was indeed hard you can tell by the number of dislike, the requirements are many and there are a lot of edge Cases I spent hours figuring how to solve it.

I first check for edge cases like when string is Empty, or has 1 non-Integer character and return false.
I decide to check whether the string is a valid integer, or a decimal number,
By writing two methods,
checkInteger, and checkDecimal,
CheckInteger convert the string to a number and if it's true return true.
check decimal checks the string and verify if its a decimal number, by verifying no characters, other than (+,-,e,E,.) and they don't appear twice.
No '.' after e.
This method works for 1438 test-cases but failed because the string can contain one of the (+,-,e,E,.) but still the are arrange in a way that makes the string invalid number e.g "4e+".

The solution is to split the input by the e or E and follow the validation rule that is check if it's integer or decimal.
"4e", "+" and apply the validation.

Leetcode problem

Implementation in python

Day 9 I4G 10daysofcodechallenge

Abubakar Sadiq Ismail — Thu, 29 Sep 2022 22:51:11 +0000

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Problem Category Hard!!!, Omo

The first idea I got was to merge the lists to a single list and the sort the whole merged lists, using a sorting algorithm, like merge sort.
Think I think of complexity and how to simplify it.
Which is why should I merge the list all.
I then get the first list,
combine the first with second link sorted,
continuously until I reach the end of the list.

Complexity is O(n+k)
Space Complexity O(k)

Problem inn leetcode
Solution Implementation in js

Day 8 I4G10daysofCodeChallenge

Abubakar Sadiq Ismail — Wed, 28 Sep 2022 20:57:07 +0000

Problem: Given a two SQL tables A,B in a database Combine them. with a common column in A and B and rows that doesn't have a common fields should return null in the B fields.

Table: Person

Table: Address

Write an SQL query to report the first name, last name, city, and state of each person in the Person table. If the address of a personId is not present in the Address table, report null instead.

Example :

Solution.

After reading through the solution I understand that what I need to do is to join Table A and B, using the LEFT JOIN.
Such that values that if some Rows in column A don't have the personId in them they should return null in the fields.

SELECT P.lastName, P.firstName, A.city, A.state
FROM Person P LEFT JOIN Address A ON P.personId = A.personId
I read about sql Joins
GeeksforGeeks SQL Join

Joining two tables

Leetcode problem

Day 7 I4G 10DaysofCodeChallenge

Abubakar Sadiq Ismail — Tue, 27 Sep 2022 22:51:59 +0000

Problem: UTF-8 Validation
Category: Medium
Given an integer array data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

For a 1-byte character, the first bit is a 0, followed by its Unicode code.
For an n-bytes character, the first n bits are all one's, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.

For UTF-8 we are going to check 4 bytes long that n=1,2,3,4..
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx
10xxxxxx

Example

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Solution
For Each interger in the input array
1.Convert to 8 bits binary representation.
For the integer 197 = 11000101

Check for n = 1,2,3 conditions.
and return the result.

Problem
Solution Implementation

Day 6 I4G 10DaysOfCodeChallenge

Abubakar Sadiq Ismail — Mon, 26 Sep 2022 22:38:49 +0000

Problem 6: Fizz Buzz Multithreaded.
Category Medium.
Given a class FizzBuzz, with 4 methods fizz (which print fizz),buzz (which print buzz),fizzBuzz (which print fizzBuzz), and printNumber( print a number).
FizzBuzz will be initialized with an integer n.
All four methods will be called from different threads.
the result of running all four threads.
Should be based on i which is 1 to n;

if i % 3 and i % 5 is 0;
return fizzBuzz
if i % 3 is 0;
return fizz
if i % 5 is 0;
return buzz
else if i % 3 and i % 5 is not 0;
return i
.
This problem as well Javascript is not in the programming language because it's single threaded.
Hence I use python to create another threads when all the threads are started.
When the last thread is started.
Iterate through n.
check the condition and call the appropriate thread or printNumber with i

Problem
Solution Implementation

Day 5 I4G 10 Days Code Challenge

Abubakar Sadiq Ismail — Sun, 25 Sep 2022 21:23:31 +0000

We are half way Day 5;
Problem: The problem is given a string you should sort it base on the character that has the highest frequency;
E.g given 'aabbbcdee'
'bbb' has highest frequency ,followed by 'aa' and 'ee' (has same frequency), then 'c' and 'd' (has same frequency).
hence the output should be 'bbbaaeecd'
Note for characters that have same frequency they can be in any order; that is the output can as well be 'bbbeeaadc';
Category: Medium we are getting their right!!!

Solution that came to my mind is to use hash map.

Step One
The Map keys are characters and the values are the characters frequency;
E.g of the map for the above Testcase will be;
{'b':3,'a':2,'e':2,'c':1,'d':1}

You can Get this by iterating through the string and creating the property or if it exist incrementing its value.

Step Two
Then create an array of arrays with two values character and the number of time it occurs;
e.g [['b',3],['a',2],['e',2],['c',1],['d',1]]
using Javascript in-built Object.entries(Object) method

Iterate through the array the create another Hash map with the keys as number of time character occurs and the value as array of the characters.
E.g
{'1':['c','d'],'2':['e','a'],3:['b']}

Get all the keys of the map using Object.keys(Object) method;
E.g ['1','2','3'];
Create the returned string
iterate through the keys starting from the highest, get all the characters and multiply it by the time it occur, increment it into the string.
Until the last key.
Return the string

Pretty Long right.

Time Complexity: O(n)
Space Complexity: O(n)
Sort Characters by frequency

Solution Implementation

Day 4 I4G Code Challenge

Abubakar Sadiq Ismail — Sat, 24 Sep 2022 22:30:34 +0000

Day 4!!!! Yay
Today's problem is interesting and challenging as well Javascript is not included in the programming language I can solve the problem with.
So I had to choose another programming language, python is always the next tool to use if Js will not solve my problem
.
The problem statement seems bizarre and a big problem but it's pretty simple and straight forward when you understand the problem.
Problem. Print In order
Tag: Easy
Given three method in a class
class foo():

firt(self):
print("first line")

second(self):
print("second line")
third(self):
print("third line")

The task is to modify the above methods such that calling
foo = foo()

foo.first()
foo.second()
foo.third()
//or
foo.first()
foo.third()
foo.second()

//or
foo.third()
foo.first()
foo.second()

Or any permutation of this calls can result in
//first line
//second line
// third line
irrespective of how they are called;

What first come to my mind is to delay third method for some time,delay second method for less time and first method will fire immediately.
So that third will wait for first and second, second will wait for first.
first fires immediately.
I use python in built time module for that.

Print Order problem

Code Implementation

Day 3 I4G 10 days of code challenge

Abubakar Sadiq Ismail — Fri, 23 Sep 2022 21:15:46 +0000

Early in the morning after I wake up, I decided to start with todays code challenge before anything else;

The problem was given an integer you return true when it's a palindrome, else return false.
Palindrome are numbers,phrase or strings that when reversed the result is the same number;
e.g 1221 is a palindrome and will return true. 1234 is not a palindrome and will return false.

The solution i think is to covert the integer to a string;
Reverse the string;
Convert the reversed string to an integer;
Compare the original integer and the reversed Integer,
If they are the same return true
Else return false

Time complexity
O(n)
Space complexity
O(n)
Leetcode problem
Link to Implementation

Day 2 I4G #10Dayscodechallenge

Abubakar Sadiq Ismail — Thu, 22 Sep 2022 22:34:31 +0000

Todays challenge was removing an Element from an array, with O(1) space complexity.
E.g given arr= [1,2,3,4,3,3,3] remove all 3 in arr
return the number of array without the element which is 3.
Question Tag: Easy

The first thing that came to my mind is to use pointer from index 0;
pointer = 0;
Iterate through the array;
If current iteration value is not the same as the element
update pointer with it;
Increment pointer

return the value of pointer;
with O(n) time complexity and O(1) space complexity;

Pseudocode
array = [...], val = x;
Pointer = 0
for item in array
if item != val
array[pointer] = item
pointer++

return pointer

Code Implementation

Leet code problem