In-place reversal modifies the original array without extra space.

Here is a general-purpose implementation:

Here is the Python code:

defreverse_array(arr):start,end=0,len(arr)-1whilestart<end:arr[start],arr[end]=arr[end],arr[start]start,end=start+1,end-1my_array= [1,2,3,4,5]print("Original Array:",my_array)reverse_array(my_array)print("Reversed Array:",my_array)

Let me put the two fundamental type of lists,Arrays andLinked Lists, into perspective.

• Array: Employs sequential memory storage and each element has a unique index.
• Linked List: Elements are scattered in memory and accessed sequentially via references (pointers).

• Array: Typically requires a single, contiguous memory block.
• Linked List: Memory allocations are dynamic and non-contiguous.

• Arrays are preferable when:

  • There's a need for direct or random access such as in lookup tables.
  • The data will remain relatively unchanged, and performance in accessing elements takes precedence over frequent insertions or deletions.

• Linked Lists are more suitable when:

  • Frequent insertions and deletions are expected, especially in the middle.
  • The exact size of the list isn't known in advance, and you want the memory to be used flexibly.
  • The primary operations are sequential, such as iteration from the beginning to the end.

Here is the Python code:

# Define arraymy_array= [10,20,30,40,50]# Access element by indexprint(my_array[2])# Output: 30# Bulk insertion at the beginningmy_array= [5,6,7]+my_arrayprint(my_array)# Output: [5, 6, 7, 10, 20, 30, 40, 50]# Deletion from the middledelmy_array[4]print(my_array)# Output: [5, 6, 7, 10, 30, 40, 50]

# Define linked list nodes (in reality, you'd have a LinkedList class)classNode:def__init__(self,data):self.data=dataself.next=None# Create linked listhead=Node(10)node1=Node(20)node2=Node(30)head.next=node1node1.next=node2# Bulk insertion at the beginningnew_node1=Node(5)new_node2=Node(6)new_node3=Node(7)new_node3.next=headhead=new_node1new_node1.next=new_node2print_nodes(head)# Output: 5, 6, 7, 10, 20, 30# Deletion from the middlenew_node1.next=new_node3# Now, just print_nodes(head) will output: 5, 6, 7, 20, 30

Checking for duplicates in an array without additional space is a common challenge with solutions using hash functions, sorting, and mathematical calculations.

The code checks for duplicates based on numerical repetition.

• Time Complexity:$O(n^2)$
• Space Complexity:$O(1)$

Here is the Python code:

defhas_duplicates(arr):n=len(arr)foriinrange(n):forjinrange(i+1,n):ifarr[i]==arr[j]:returnTruereturnFalsearr= [1,2,3,4,3]print(has_duplicates(arr))# Output: True

This method involves sorting the array using acomparison-based sorting algorithm like Quick Sort. If two adjacent elements are the same, then the array has duplicates.

• Time Complexity: Best/Worst:$O(n \log n)$
• Space Complexity:$O(1)$ or$O(n)$ depending on sorting algorithm

Here is the Python code:

defhas_duplicates_sorted(arr):arr.sort()n=len(arr)foriinrange(n-1):ifarr[i]==arr[i+1]:returnTruereturnFalsearr= [1,2,3,4,3]print(has_duplicates_sorted(arr))# Output: True

For this method,the sum of numbers in the array is calculated. Mathematically, if no duplicates are present, the sum of consecutive natural numbers can be calculated to compare against the actual sum.

If$\text{actual sum} - \text{sum of numbers in the array} = 0$, there are no duplicates.

Here is the Python code:

defhas_duplicates_math(arr):array_sum=sum(arr)n=len(arr)expected_sum= (n* (n-1))//2# Sum of first (n-1) natural numbersreturnarray_sum-expected_sum!=0arr= [1,2,3,4,5,5]print(has_duplicates_math(arr))# Output: True

Let's look at the high-levelstrategy behind binary search and then walk through astep-by-step example.

1. Divide & Conquer: Begin with the entire sorted array and refine the search range in each step.
2. Comparison: Use the middle element to determine the next search range.
3. Repetition: Continue dividing the array until the target is found or the search range is empty.

Let's consider the following array with the target value of17:

[1, 3, 6, 7, 9, 12, 15, 17, 20, 21]

1. Initial Pointers: We start with the whole array.

   [1, 3, 6, 7, 9, 12, 15, 17, 20, 21]  ^                               ^Low                             HighMiddle: (Low + High) / 2 = 5

   This identifies theMiddle number as12.

2. Comparison: Since theMiddle number is less than the target17, we candiscard the left portion of the array.

   [15, 17, 20, 21]^           ^Low        High

3. Updated Pointers: We now have a reduced array to search.

   Middle = 7^      ^Low   High

4. Final Comparison:
   Since theMiddle number is now the target,17, the search is successfully concluded.

Rotating a 2D array by$90^\circ$ can be visually understood as atranspose followed by areversal of rows or columns.

1. Transpose: Swap each element$A[i][j]$ with its counterpart$A[j][i]$
2. Reverse Rows (for$90^\circ$ CW) or Columns (for$90^\circ$ CCW)

• Time Complexity: Both steps run in$O(n^2)$ time.
• Space Complexity: Since we do an in-place rotation, it's$O(1)$.

Here is the Python code:

defrotate_2d_clockwise(matrix):n=len(matrix)# Transposeforiinrange(n):forjinrange(i,n):matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]# Reverse Rowsforiinrange(n):forjinrange(n//2):matrix[i][j],matrix[i][n-j-1]=matrix[i][n-j-1],matrix[i][j]returnmatrixdefrotate_matrix_ccw(matrix):n=len(matrix)# Transposeforiinrange(n):forjinrange(i,n):matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]# Reverse Columnsforiinrange(n):forjinrange(n//2):matrix[j][i],matrix[n-j-1][i]=matrix[n-j-1][i],matrix[j][i]returnmatrix# Testmatrix= [[1,2,3], [4,5,6], [7,8,9]]print(rotate_2d_clockwise(matrix))# Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

You can compress a string following the count of each character. For example, "aabbccc" becomes "a2b2c3".

The python code for this algorithm is:

defcompress_string(input_string):# Initializecurrent_char=input_string[0]char_count=1output=current_char# Iterate through the stringforcharininput_string[1:]:# If the character matches the current one, increment countifchar==current_char:char_count+=1else:# Append the count to the output and reset for the new characteroutput+=str(char_count)+charcurrent_char=charchar_count=1# Append the last character's countoutput+=str(char_count)# If the compressed string is shorter than the original string, return itreturnoutputiflen(output)<len(input_string)elseinput_string

This algorithm has a time complexity of$O(n)$ since it processes each character of the input string exactly once.

The space complexity is$O(k)$, where$k$ is the length of the compressed string. This is because theoutput string is stored in memory.

Let's look at what is anArray Slice and how it's implemented in some programming languages.

An array slice is a view on an existing array that acts as a smaller array. The slice references a continuous section of the original array which allows for efficient data access and manipulation.

Array slices are commonly used in languages likePython,Rust, andGo.

• Read: Access elements in the slice.
• Write: Modify elements within the slice.
• Grow/Shrink: Resize the slice, often DWARF amortized.
• Iteration: Iterate over the elements in the slice.

A slice typically contains:

1. Apointer to the start of the slice.
2. Thelength of the slice (the number of elements in the slice).
3. Thecapacity of the slice (the maximum number of elements that the slice can hold).

• No Copy Overhead: Slices don't duplicate the underlying data; they're just references. This makes them efficient and memory-friendly.
• Flexibility: Slices can adapt as the array changes in size.
• Safety: Languages likeRust use slices for enforcing safety measures, preventing out-of-bounds access and memory issues.

• Python: Uses list slicing, with syntax likemy_list[2:5]. This creates a new list.

• Go Lang: Employs slices extensively and is perhaps the most slice-oriented language out there.

• Rust: Similar to Go, it's a language heavily focused on memory safety, and slices are fundamental in that regard.

Here is thePython code:

original_list= [1,2,3,4,5]my_slice=original_list[1:4]# Creates a new list: [2, 3, 4]

Here is theRust code:

let original_vec =vec![1,2,3,4,5];let my_slice =&original_vec[1..4];// References a slice: [2, 3, 4]

And here is theGo code:

originalArray:= [5]int{1,2,3,4,5}mySlice:=originalArray[1:4]// References the originalArray from index 1 to 3

Botharray insertions anddeletions have a time complexity of$O(n)$ due to potential need for data re-arrangement.

• Beginning:$O(n)$ if array full;$1$ for shifting.
• Middle:$O(n)$ to make room and insert.
• End:$O(1)$ on average for appending.

• Beginning:$O(n)$ due to re-arrangement often needed.
• Middle:$O(n)$ as it involves shifting.
• End:$O(1)$ for most cases, but$O(n)$ when dynamic resizing is required.

Merging two sorted arrays into a new sorted array can be accomplished through a variety of well-established techniques.

1. Using Additional Space:

   • Create a new array and add elements from both arrays using two pointers, then return the merged list.
   • Time Complexity:$O(n + m)$ - where$n$ and$m$ are the number of elements in each array. This approach is simple and intuitive.

2. Using a Min Heap:

   • Select the smallest element from both arrays using a min-heap and insert it into the new array.
   • Time Complexity:$O((n + m) \log (n + m))$
   • Space Complexity:$O(n + m)$ - Heap might contain all the elements.
   • This approach is useful when the arrays are too large to fit in memory.

3. In-Place Merge:

   • Implement a merge similar to the one used inMerge Sort, directly within the input array.
   • Time Complexity:$O(n \cdot m)$ - where$n$ and$m$ are the number of elements in each array.
   • In-Place Merging becomes inefficient as the number of insertions increases.

4. Using Binary Search:

   • Keep dividing the larger array into two parts and using binary search to find the correct position for elements in the smaller array.
   • Time Complexity:$O(m \log n)$

5. Two-Pointer Technique:

   • Initialize two pointers, one for each array, and compare them to determine the next element in the merged array.
   • Time Complexity:$O(n + m)$

To find the$k^{\text{th}}$ largest element in an unsorted array, you canleverage heaps or quicksort.

• Idea: Partition the array using a pivot (similar to quicksort) and divide into subarrays until the partitioning index is the$k^{\text{th}}$ largest element.

• Time Complexity:

  • Worst-case:$O(n^2)$ - This occurs when we're faced with the least optimized scenario, reducing$n$ by only one element for each stitch step.
  • Average-case:$O(n)$ - Average performance is fast, making the expected time complexity linear.

• Code Example: Python

  importrandomdefquickselect(arr,k):ifarr:pivot=random.choice(arr)left= [xforxinarrifx<pivot]right= [xforxinarrifx>pivot]equal= [xforxinarrifx==pivot]ifk<len(left):returnquickselect(left,k)elifk<len(left)+len(equal):returnpivotelse:returnquickselect(right,k-len(left)-len(equal))

• Build amax-heap$O(n)$ - This takes linear time, making$O(n) + O(k \log n) = O(n + k \log n)$.
• Extract the max element$k$ times (each time re-heapifying the remaining elements).

importheapqdefkth_largest_heap(arr,k):ifk>len(arr):returnNoneneg_nums= [-iforiinarr]heapq.heapify(neg_nums)k_largest= [heapq.heappop(neg_nums)for_inrange(k)]return-k_largest[-1]

Singly linked lists anddoubly linked lists differ in how they manage node-to-node relationships.

• Singly Linked List: Each node points to the next node.

• Doubly Linked List: Both previous and next nodes are pointed to.

• Access Direction: Singly linked lists facilitate one-way traversal, while doubly linked lists support bi-directional traversal.

• Head and Tail Movements: Singly linked lists only operate on the head, while doubly linked lists can manipulate the head and tail.

• Backward Traversal Efficiency: Due to their structure, singly linked lists may be less efficient for backward traversal.

• Memory Requirement: Doubly linked lists use more memory as each node carries an extra pointer.

Here is the Java code:

publicclassSinglyLinkedList {privatestaticclassNode {privateintdata;privateNodenext;publicNode(intdata) {this.data =data;this.next =null;        }    }privateNodehead;publicvoidinsertFirst(intdata) {NodenewNode =newNode(data);newNode.next =head;head =newNode;    }publicvoiddisplay() {Nodecurrent =head;while (current !=null) {System.out.println(current.data);current =current.next;        }    }}

Here is the Java code:

publicclassDoublyLinkedList {privatestaticclassNode {privateintdata;privateNodeprevious;privateNodenext;publicNode(intdata) {this.data =data;this.previous =null;this.next =null;        }    }privateNodehead;privateNodetail;publicvoidinsertFirst(intdata) {NodenewNode =newNode(data);if (head ==null) {head =newNode;tail =newNode;        }else {head.previous =newNode;newNode.next =head;head =newNode;        }    }publicvoiddisplay() {Nodecurrent =head;while (current !=null) {System.out.println(current.data);current =current.next;        }    }publicvoiddisplayBackward() {Nodecurrent =tail;while (current !=null) {System.out.println(current.data);current =current.previous;        }    }}

Cycle detection in a linked list is a fundamental algorithm that uses pointers to identify if a linked list has a repeating sequence.

Floyd's algorithm utilizes two pointers:

• The "tortoise" moves one step each iteration.
• The "hare" moves two steps.

If the linked list does not have a cycle, the hare either reaches the end (or null) before the tortoise, or vice versa. However, if there is a cycle, the two pointersare guaranteed to meet inside the cycle.

1. Initialize both pointers to the start of the linked list.
2. Move the tortoise one step and the hare two steps.
3. Continuously advance the pointers in their respective steps:
   • If the tortoise reaches the hare (a collision point), return such a point.
   • If either pointer reaches the end (null), conclude there is no cycle.

• Time Complexity:$O(n)$ where$n$ is the number of nodes in the linked list, due to each pointer visiting each node only once.
• Space Complexity:$O(1)$ as the algorithm uses only a constant amount of extra space.

Here is the Python code:

defhas_cycle(head):tortoise=headhare=headwhilehareandhare.next:tortoise=tortoise.nexthare=hare.next.nextiftortoise==hare:returnTruereturnFalse

Let's look at the major operations you can perform on asingly linked list and their associated time complexities:

• Head: Constant time:$O(1)$.
• Tail:$O(n)$ without a tail pointer, but constant with a tail pointer.
• Middle or k-th Element:$\frac{n}{2}$ is around the middle node; getting k-th element requires$O(k)$.

• Unordered: May require scanning the entire list. Worst case:$O(n)$.
• Ordered: You can stop as soon as the value exceeds what you're looking for.

• Head:$O(1)$
• Tail:$O(1)$ with a tail pointer, otherwise$O(n)$.
• Middle:$O(1)$ with tail pointer and finding position in$O(1)$ time; otherwise, it's$O(n)$.

• Head:$O(1)$
• Tail:$O(n)$ because you must find the node before the tail for pointer reversal with a single pass.
• Middle:$O(n)$ since you need to find the node before the one to be deleted.

• Naive: Requires a full traversal. Every addition or removal requires this traversal.
• Keep Count: Maintain a separate counter, updating it with each addition or removal.

Here is the Python code:

classNode:def__init__(self,data):self.data=dataself.next=NoneclassSinglyLinkedList:def__init__(self):self.head=Nonedefappend(self,data):# O(n) without tail pointernew_node=Node(data)ifnotself.head:self.head=new_nodereturnlast_node=self.headwhilelast_node.next:last_node=last_node.nextlast_node.next=new_nodedefdelete(self,data):# O(n) only if element is not at headcurrent_node=self.headifcurrent_node.data==data:self.head=current_node.nextcurrent_node=Nonereturnwhilecurrent_node:ifcurrent_node.data==data:breakprev=current_nodecurrent_node=current_node.nextifcurrent_nodeisNone:returnprev.next=current_node.nextcurrent_node=Nonedefget_middle(self):# O(n)slow,fast=self.head,self.headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextreturnslowdefget_kth(self,k):# O(k)current_node,count=self.head,0whilecurrent_node:count+=1ifcount==k:returncurrent_nodecurrent_node=current_node.nextreturnNone# Other methods: display, length, etc.

In-Place Algorithms modify data structures with a constant amount of extra working space$O(1)$.

ASingly Linked List presents a straightforward example of an in-place data structure, well-suited for in-place reversal algorithms.

The reversal algorithm just needs to update each node'snext reference so that they point to the previous node. A few key steps achieve this:

1. Initialize: Keep track of the three key nodes:previous,current, andnext.
2. Reverse Links: Update each node to instead point to the previous one in line.
3. Move Pointers: Shiftprevious,current, andnext nodes by one position for the next iteration.

This process proceeds iteratively untilcurrent reaches the end, i.e.,NULL.

• Time Complexity: The algorithm exhibits a linear time complexity of$O(n)$ as it visits each node once.
• Space Complexity: As the algorithm operates in-place, only a constant amount of extra space (for nodes pointers) is required:$O(1)$.

Here is the Python code:

classNode:def__init__(self,data=None):self.data=dataself.next=NoneclassLinkedList:def__init__(self):self.head=Nonedefappend(self,data):new_node=Node(data)ifnotself.head:self.head=new_nodereturnlast_node=self.headwhilelast_node.next:last_node=last_node.nextlast_node.next=new_nodedefreverse_inplace(self):previous=Nonecurrent=self.headwhilecurrent:next_node=current.nextcurrent.next=previousprevious=currentcurrent=next_nodeself.head=previousdefdisplay(self):elements= []current=self.headwhilecurrent:elements.append(current.data)current=current.nextprint(" -> ".join(str(data)fordatainelements))# Populate the linked listllist=LinkedList()values= [4,2,8,3,1,9]forvalueinvalues:llist.append(value)# Display originalprint("Original Linked List:")llist.display()# Reverse in-place and displayllist.reverse_inplace()print("\nAfter Reversal:")llist.display()

Finding the middle element of a linked list is a common problem with several efficient approaches, such as thetwo-pointer (or "runner") technique.

The two-pointer technique uses two pointers, often namedslow andfast, to traverse the list. Whilefast moves two positions at a time,slow trails behind, covering a single position per move. Whenfast reaches the end,slow will be standing on the middle element.

Given the linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

The pointers will traverse as follows:

• (1)slow: 1;fast: 2
• (2)slow: 2;fast: 4
• (3)slow: 3;fast: 6
• (4)slow: 4;fast: end

At (4), theslow pointer has reached the middle point.

• Time Complexity:$O(N)$ -- For every N nodes, we check each node once.
• Space Complexity:$O(1)$ -- We only use pointers; no extra data structures are involved.

Here is the Python implementation:

deffind_middle_node(head):ifnothead:returnNoneslow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextreturnslow