DEV Community: Andres Ramirez

C# Priority Queue

Andres Ramirez — Mon, 29 Apr 2024 14:50:09 +0000

Imagine a heap as a special kind of tree where each parent node has a value that's less than or equal to the values of its children. In simpler terms, you can think of it as a tree where the parent node is always smaller (or larger) than its children. This property makes heaps perfect for priority queues, where the topmost element (root) always has the highest (or lowest) priority.

By default, the .NET class PriorityQueue provide us with a Min Heap. This means that the smallest element is always at the root (every parent node has a value less than or equal to the values of its children), however, we are allowed to pass a "Comparer" function to modify this behavior.

This is what I want to show you in this article. We are going to implement a Max Heap using the Priority Queue class, introduced in .NET 6

We will resolve this leetcode exercise:

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

Solution: This method initializes two priority queues, pqOdd and pqEven, to store odd and even digits respectively in descending order. It then iterates through each digit of the input number, enqueuing them into the appropriate priority queue based on their parity (odd or even) and marking their position in the result list accordingly. After all digits are processed, it dequeues the digits from the priority queues in the order specified by the result list, effectively rearranging them to form the largest integer possible. Finally, it converts the rearranged digits back into an integer and returns it.

Note that we pass a Comparer function and therefore achieve the behavior of the priority queue as a max heap

public class Solution
{
    // Method to find the largest possible integer by rearranging the digits of the input number
    public int LargestInteger(int num)
    {
        // Initialize two priority queues to store digits: pqOdd for odd digits and pqEven for even digits
        // Priority queues are initialized with custom comparers to ensure descending order
        PriorityQueue<int, int> pqOdd = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        PriorityQueue<int, int> pqEven = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));

        // List to store the result digits
        List<int> result = new List<int>();

        // Iterate through each digit of the input number
        foreach (char digit in num.ToString())
        {
            // Convert the character digit to an integer
            int digitInt = int.Parse(digit.ToString());

            // Check if the digit is even or odd
            if (digitInt % 2 == 0) {
                // If even, enqueue the digit into pqOdd with the digit itself as priority
                pqOdd.Enqueue(digitInt, digitInt);
                // Add 0 to the result list to mark the position of the even digit
                result.Add(0);
            }
            else {
                // If odd, enqueue the digit into pqEven with the digit itself as priority
                pqEven.Enqueue(digitInt, digitInt);
                // Add 1 to the result list to mark the position of the odd digit
                result.Add(1);
            };
        }

        // Iterate through the result list to rearrange the digits
        for (int i = 0; i < result.Count(); i++)
        {
            // If the result at index i is 0, dequeue the top element from pqOdd and update the result list
            if (result[i] == 0)
            {
                result[i] = pqOdd.Dequeue();
            }
            // If the result at index i is 1, dequeue the top element from pqEven and update the result list
            else
            {
                result[i] = pqEven.Dequeue();
            }
        }

        // Convert the result list to a string and then to an integer, and return it
        return int.Parse(string.Join("", result));
    }
}

C# Stacks

Andres Ramirez — Thu, 28 Mar 2024 17:55:28 +0000

A stack follows the Last In, First Out (LIFO) or First In, Last Out (FILO) order, which means that the last element added to the stack is the first one to be removed.

To manage a stack, a pointer to the top is maintained, allowing access only to the top element.

Basic operations include push, pop, peek, isempty, top, and size.

Two types of stacks exist: dynamic (adjusting size dynamically) and static (fixed size).

Stacks can be implemented using arrays or linked lists.

Implementing Stack using Arrays

Implementing Stack a Linked List

Implement a stack using singly linked list

using System;

// Create Stack Using Linked list
public class StackUsingLinkedlist {

    // A linked list node
    private class Node {
        // integer data
        public int data;

        // reference variable Node type
        public Node link;
    }

    // create global top reference variable
    Node top;

    // Constructor
    public StackUsingLinkedlist() { this.top = null; }

    // Utility function to add
    // an element x in the stack
    // insert at the beginning
    public void push(int x)
    {
        // create new node temp and allocate memory
        Node temp = new Node();

        // check if stack (heap) is full.
        // Then inserting an element
        // would lead to stack overflow
        if (temp == null) {
            Console.Write("\nHeap Overflow");
            return;
        }

        // initialize data into temp data field
        temp.data = x;

        // put top reference into temp link
        temp.link = top;

        // update top reference
        top = temp;
    }

    // Utility function to check if
    // the stack is empty or not
    public bool isEmpty() { return top == null; }

    // Utility function to return
    // top element in a stack
    public int peek()
    {
        // check for empty stack
        if (!isEmpty()) {
            return top.data;
        }
        else {
            Console.WriteLine("Stack is empty");
            return -1;
        }
    }

    // Utility function to pop top element from the stack
    public void pop() // remove at the beginning
    {
        // check for stack underflow
        if (top == null) {
            Console.Write("\nStack Underflow");
            return;
        }

        // update the top pointer to
        // point to the next node
        top = (top).link;
    }

    public void display()
    {
        // check for stack underflow
        if (top == null) {
            Console.Write("\nStack Underflow");
            return;
        }
        else {
            Node temp = top;
            while (temp != null) {

                // print node data
                Console.Write(temp.data);

                // assign temp link to temp
                temp = temp.link;
                if(temp != null)
                    Console.Write(" -> ");
            }
        }
    }
}

// Driver code
public class GFG {
    public static void Main(String[] args)
    {
        // create Object of Implementing class
        StackUsingLinkedlist obj
            = new StackUsingLinkedlist();

        // insert Stack value
        obj.push(11);
        obj.push(22);
        obj.push(33);
        obj.push(44);

        // print Stack elements
        obj.display();

        // print Top element of Stack
        Console.Write("\nTop element is {0}\n", obj.peek());

        // Delete top element of Stack
        obj.pop();
        obj.pop();

        // print Stack elements
        obj.display();

        // print Top element of Stack
        Console.Write("\nTop element is {0}\n", obj.peek());
    }
}

Multiple Pointers | C#

Andres Ramirez — Tue, 26 Mar 2024 12:59:15 +0000

What is this all about?

Used for searching pairs in a SORTED array
Create pointers that correspond to an index and move towards the beginning, end or middle based on a certain condition.
We are able to process two or more elements per loop instead of just one.

When do we use it?

In many problems involving collections such as arrays or lists, we have to analyze each element of the collection compared to its other elements.

Common patterns

Two pointers, each starting from the beginning and the end until they both meet.
One pointer moving at a slow pace, while the other pointer moves at twice the speed.

--- Problem
    We are asked to compare two elements in an ordered array.

--- FOOR LOOP
     If we use a for loop, we create an external pointer and use the 
     internal "j" as the second pointer.
         var i = 0;          
         for(var j = 1; j < array.length; j++){  
                if(arr[i] !== arr[j]){
                    i++; 
                    arr[i] = arr[j]
                }

--- WHILE LOOP
    If we use a while loop we create two external pointers and the  
    base one case is while left<right {}. This structure is used when 
    we need to traverse the array from two opposite points. 

        let left = 0                       <-- pointer 1
        let right = array.length - 1       <-- pointer 2
        while (left < right) {
            let average = array[left] + array[right] / 2 
            if (average === target) return true; 
            else if(average < target) left++
            else right--  
        }
        return false 
    }

In action

Implement a function called countUniqueValues, which accepts a sorted array, and counts the unique values in the array.

Code to resolve this:

Frequency Counter Technique in C#

Andres Ramirez — Thu, 21 Mar 2024 22:08:30 +0000

How to identify it?

Querying item presence in A against B.
Prioritizing linear time complexity (O(n)) over quadratic (O(n²)), avoiding nested loops.

TO ACCOMPLISH THIS OBJECTIVE...

Utilize individual O(n) loops instead of nested loops for efficiency.
Employ object mapping to facilitate element comparison.
Establish keys as elements and values as their respective frequencies.

---Pseudocode
            A) Iterate through the array 
            B) Grab the value of each item in the array and set it to variable key 
            C) If key exists as a key in myObject... 
            D) ... increment it by 1 
            E) If not (key doesn't exist in myObject)... 
            F) ... create key in myObject and set it equal to 1

FREQUENCY COUNTER IN ACTION

Problem: Write a function frequencyCounter, which accepts two arrays. The function should return true if every value in the array has its corresponding value squared in the second array. The frequency values must be the same.

Code to solve this problem:

Mapping each list's elements to their frequencies in separate dictionaries enables efficient comparison, ensuring a streamlined process. This technique sidesteps nested loops, resulting in a time complexity of O(n) and superior efficiency compared to alternative methods.

With two individual loops, each element in the arrays is processed separately, allowing for direct comparison and frequency counting. Nested loops, on the other hand, would lead to redundant comparisons between every pair of elements, resulting in unnecessary computations.

ADDITIONAL EXERCISES:

C# Linked Lists: Exploring Dummy Nodes, Pointers, and More | Data Structures

Andres Ramirez — Wed, 20 Mar 2024 17:37:22 +0000

Implementing a Linked List (LL) involves creating a linear data structure with interconnected nodes. Utilizing pointers, such as 'Head' and 'Tail,' involves variables pointing to the memory locations of the first and last elements in the LL, respectively.

An essential concept in Linked Lists (LL) is their dependence on references rather than indexes. Navigating to a specific point, such as D, entails methodically traversing the sequence A → B → C → D.

🔄IMPLEMENTATION

This code initializes a linked list with a single node containing a specified value. The LinkedList class includes a private Node class with properties for value and next, and a constructor that creates a new node and sets both head and tail to reference it, initializing the length to 1.

📝LINKED LISTS TYPES

Single LL: Each node in the list contains a reference (or pointer) to the next node in the sequence. The last node points to null, indicating the end of the list.
Doubly LL: Each node contains references to both the next and the previous nodes in the sequence. Allows traversal in both forward and backward directions.
Circular LL: Similar to a singly linked list, but the last node points back to the first node, forming a circular structure. Can be implemented with a singly linked list or a doubly linked list.

✏️BASIC OPERATIONS

To establish a robust foundation in Linked Lists, proficiency in the following key areas is imperative:

Get: Retrieve information from the Linked List.
Update: Modifying existing elements within the Linked List.
Insertion: Manage the addition of elements within the Linked List structure.
Deletion: Handle the removal of elements from the Linked List.
Reverse: Change the order of elements in the list so that the last node becomes the first and vice versa.

Get familiar with the Basic LL operations

📈FUNDAMENTALS FOR EXPLORING MORE COMPLEX LL EXERCISES

Linked Lists and Reference Types: In Linked Lists, nodes are reference types. This means that any operation affecting a node will also affect any pointer that points to it.
Pointer: A pointer is a variable that stores the memory address of another variable or object. In linked lists, pointers are used to keep track of the connections between nodes.
Dummy Node: A dummy node is a special node added at the beginning of a linked list to simplify certain operations. It does not hold meaningful data and is used as a placeholder.

CODING, CODING AND CODING...

The best way to illustrate these concepts is if we explore some exercises.

Linked List Cicle

Checkout this PROBLEM. We need to validate if a LL has cycle in it. This is a perfect example to illustrate the use of pointers.

Code to solve this problem:

Explanation:

Pointers (fast and slow) are essential for traversing a linked list, enabling movement from one node to the next. Without them, iterating through and examining nodes would be impossible.
By moving a fast pointer twice as fast as a slow pointer, the algorithm efficiently identifies whether a cycle exists in the list.

Remove Duplicates from Sorted List II

In this problem, we need to delete all nodes that have duplicate numbers. This is a perfect example to illustrate the use of a dummy node.

Code to solve this problem:

It's important to note that we create a dummy node which always points to the head. This is convenient because even if the node pointed to by "head" changes, we'll always have a constant reference to the new value in question.

This case teaches us that WE CAN USE A DUMMY NODE IN SITUATIONS WHERE THE HEAD OR THE LINKED LIST ITSELF MAY UNDERGO CHANGES AS THEY GO THROUGH OUR CODE.

Merge Two Sorted Lists

In this problem we need to merge the two lists into one (new) sorted list. This is a very good example of using a dummy node, but with a different approach.

Code to solve this problem:

The dummy node acts as a placeholder for the merged list. It ensures that current always points to a valid node, even if the first node of the merged list changes during the merging process.
Inside the loop, the value of current is updated iteratively based on the values of the nodes in list1 and list2. By using a dummy node, we can avoid special handling for the first node of the merged list.
After the loop, the next pointer of the last node (current) points to the remaining nodes of either list1 or list2. The dummy node's next pointer (dummy.next) then serves as the head of the merged list.

CONCLUSION

Understanding pointers and dummy nodes is crucial for effectively solving complex problems involving linked lists. Pointers facilitate efficient traversal and manipulation of linked list elements, while dummy nodes provide a consistent starting point for various operations, simplifying code logic. Additionally, grasping the reference type nature of nodes in linked lists helps in managing node connections and ensuring proper list manipulation. Together, these concepts empower developers to tackle intricate linked list problems with clarity and efficiency.

C# ARRAYS | DATA STRUCTURE.

Andres Ramirez — Wed, 20 Mar 2024 13:36:23 +0000

Arrays are fundamental data structures that allow you to store multiple values of the same data type in a single variable.

🔢ARRAY PROPERTIES AND LIMITATIONS

Array dimensions are set upon declaration, with lengths determined during instantiation, remaining immutable thereafter.
Elements in an array are accessed using an index.
All elements in an array must be of the same data type.
Accessing an index beyond the array's bounds triggers a runtime exception.
When passing an array as a parameter to a method, you are passing a reference to the array, not a copy of the entire array.
Arrays can be single-dimensional, multidimensional, or jagged.
Unlike lists and other data structures, arrays lack built-in methods for typical operations such as element addition, removal, or sorting

🧩ARRAY TYPES

Single-dimensional array: An array containing elements arranged in a single line. Accessed using a single index. Represented as a linear collection of elements.
Two-dimensional array: An array containing elements arranged in rows and columns. Accessed using two indices, one for the row and one for the column. Represents a table-like structure of data.
Three-dimensional array: An array containing elements arranged in a three-dimensional space. Accessed using three indices, representing depth, row, and column. Represents a cube-like structure of data.
Jagged array: An array whose elements are arrays themselves. Each sub-array can have a different length. Provides flexibility in representing irregular or non-rectangular data structures.

📦INITIALIZATION

📚ARRAY CLASS

C# offers an Array class to handle various array-related operations. Equipped with methods for creating, manipulating, searching, and sorting array elements, this class serves as the foundational framework for all arrays within the .NET programming ecosystem.
Learn more

DEV Community: Andres Ramirez

C# Priority Queue

C# Stacks

Implementing Stack using Arrays

Implementing Stack a Linked List

Multiple Pointers | C#

What is this all about?

When do we use it?

Common patterns

In action

Frequency Counter Technique in C#

How to identify it?

TO ACCOMPLISH THIS OBJECTIVE...

FREQUENCY COUNTER IN ACTION

ADDITIONAL EXERCISES:

C# Linked Lists: Exploring Dummy Nodes, Pointers, and More | Data Structures

🔄IMPLEMENTATION

📝LINKED LISTS TYPES

✏️BASIC OPERATIONS

📈FUNDAMENTALS FOR EXPLORING MORE COMPLEX LL EXERCISES

CODING, CODING AND CODING...

Linked List Cicle

Remove Duplicates from Sorted List II

Merge Two Sorted Lists

CONCLUSION

C# ARRAYS | DATA STRUCTURE.

🔢ARRAY PROPERTIES AND LIMITATIONS

🧩ARRAY TYPES

📦INITIALIZATION

📚ARRAY CLASS

🎯ADDITIONAL RESOURCES