Unique Email Addresses in Python

Every email consists of a local name and a domain name, separated by the @ sign.

For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.

Besides lowercase letters, these emails may contain '.'s or '+'s.

If you add periods ('.') between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name.  For example, "alice.z@leetcode.com" and "alicez@leetcode.com" forward to the same email address.  (Note that this rule does not apply for domain names.)

If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com.  (Again, this rule does not apply for domain names.)

It is possible to use both of these rules at the same time.

Given a list of emails, we send one email to each address in the list.  How many different addresses actually receive mails? 

Input: ["test.email+alex@leetcode.com", "test.e.mail+bob.cathy@leetcode.com",

 "testemail+david@lee.tcode.com"]
Output: 2Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com"actually
receive
mails

Example Note:

• 1 <= emails[i].length <= 100
• 1 <= emails.length <= 100
• Each emails[i] contains exactly one '@' character.
• All local and domain names are non-empty.
• Local names do not start with a '+' character.

class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        seen = set()
        for email in emails:
            local, domain = email.split('@')
            if '+' in local:
                local = local[:local.index('+')]
            seen.add(local.replace('.', '') + '@' + domain)
        return len(seen)

Time Complexity : O(n)

Space Complexity : O(n)

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Java Solution : O(n) space and O(n) time complexity

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public boolean hasCycle(ListNode head) {

        Set<ListNode> nodeSeen = new HashSet<>();

        while(head !=null){

            if(nodeSeen.contains(head))

                return true;

            else

                nodeSeen.add(head);

            head=head.next;

        }

        return false;

    }

}

Java Solution : O(n) Time Complexity O(1) Space Complexity

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public boolean hasCycle(ListNode head) {

        ListNode fast = head;

        ListNode slow = head;

        while(fast!=null&&fast.next!=null){

            slow = slow.next;

            fast = fast.next.next;

            if(slow==fast)

                return true;

        }

        return false;

    }

}

ValueError: need more than 2 values to unpack

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: need more than 2 values to unpack

Solution :

No of variables should be equal to no of elements in sequence or tuple.

Example :

data = [25,"Satya","G",(8,31,2010)]
age,fname,lname,dob = data
print("My name ",fname+lname," and age ",age," dob ",dob)
age,fname,lname,(month,day,year) = data
print("My name ",fname+lname," and age ",age," and year i born :",year)

Single Number - LeetCode

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

Java Solution :

class Solution {
    public int singleNumber(int[] nums) {
        if(nums == null) return 0;
        int result = 0;
        for(int i=0;i<nums.length;i++){
            result ^= nums[i];
        }
        return result;
    }
}

Pascal's Triangle II - LeetCode

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3
Output: [1,3,3,1]

Java Solution :

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>();
        result.add(1);
        if(rowIndex == 0)
            return result;
        for(int i = 1; i <=  rowIndex ; i++){
            for(int j = i-1;j > 0; j--){
                result.set(j,result.get(j-1)+result.get(j));
            }
            result.add(1);
        }
        return result;
    }
}

Pascal's Triangle - LeetCode

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Java Solution :

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(numRows == 0)
           return result;
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        result.add(row);
        for(int i=1;i<numRows;i++){
            List<Integer> prevRow = new ArrayList<Integer>();
            prevRow = result.get(i-1);
            row = new ArrayList<>();
            row.add(1);
            for(int j=1 ; j < i ; j++){
                row.add(prevRow.get(j-1)+prevRow.get(j));
            }
            row.add(1);
          result.add(row);
        }
        return result;
    }
}

Time Complexity : O(n*n)

Space Complexity : O(n*n)

Data Structures and Algorithms Tutorial

Why Sorting ?

Sorting is  used to order the elements or data in increasing or decreasing order or in lexicographical order.

More than 25% of time spent on sorting in computing .

Use Cases :

1. For searching , sorting is a kind of pre-computation done on data. So that element can be easily found.

2. Sorting is used to find duplicates in a group of elements.

   i.e when you sort all the elements will be in order and duplicate elements will be next to each other and easily be found. (Duplicates will be in consecutive)

3. Matching items in two files . When you sort the two files and matching items can be easily found in single pass.

   i.e This can be implemented using merge sort.

4. Median can be easily when sorted.

    i.e After sorted middle element will be the median.

5. Top K minimum or maximum elements.

6.  Truncated top of items that are relevant to our search.

Ex : Facebook feed , Google search , Gmail search , Twitter feed , Instagram feed , Airbnb homes search , Amazon search bar results.


Main Usage :

1. How to attack new problems .

Algorithm design strategies like Divide and Conquer and Decrease and Conquer.

2.  To analyse algorithms to determine their performance. So that you can choose between two competing solutions of a problem.

Brute Force Design Strategy :

Brute Force is a simplest and straight forward design strategy based up on the problem statement.

Selection Sort :

Selection sort means iterate over the unsorted array and find the minimum element and place it in it's right position.

An algorithm efficiency is determined by it's time and space complexity.

Selection sort Algorithm :

Java Solution :

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Java Solution : Selection Sort

class Solution {

    public List<Integer> sortArray(int[] nums) {

        List<Integer> sortedList = new ArrayList<>();

        for(int i = 0; i < nums.length;i++){

            int minimumValueIndex = i;

            for(int j=i+1; j < nums.length;j++){

                if(nums[j] < nums[minimumValueIndex]){

                    minimumValueIndex = j;

                }

            }

            if(i != minimumValueIndex){ // To skip this loop when elements at both indexes are equal.

                int temp = nums[i];

                nums[i] = nums[minimumValueIndex];

                nums[minimumValueIndex] = temp;

            }

        }   

        for(int i=0;i < nums.length;i++){

            sortedList.add(new Integer(nums[i]));

        }

        return sortedList;

    }

}



Time Complexity : O(n*n) because two for loops.

Space Complexity : O(n) space for LinkedList

Bubble Sort :

Java Solution : Bubble Sort

class Solution {

    public List<Integer> sortArray(int[] nums) {

        // Bubble Sort

        // In bubble sort we will iterate from right to left and bubble up if we find any right element is less than it's left element and in each iteration minimum element will come to it's position.

        // Bubble sort is a variant of brute force approach.

        List<Integer> sortedList = new ArrayList<>();

        int temp = 0;

        for(int i = 1 ;i < nums.length;i++){

            for(int j = nums.length-1; j > 0 ; j--){

                if(nums[j-1] > nums[j]){

                    temp = nums[j];

                    nums[j] = nums[j-1];

                    nums[j-1] = temp;

                }

            }

        }

        for(int num : nums){

            sortedList.add(new Integer(num));

        }

        return sortedList;

    }

}

Time Complexity : O(n*n) n is no fo iterations . other n for number of swaps.

Space Complexity : O(n)