We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Data Structures
  3. Arrays
  4. Sparse Arrays
  5. Discussions

Sparse Arrays

  • gerald_edward_b1 + 5 comments

    Here is a solution that actually uses the notion of "Sparse Arrays" (if you used Maps or LINQ you really missed the point of the exercise):

    using System;
using System.Collections.Generic;
using System.IO;

class Solution {
    
    public class Node {
        
        private int count = 0;
        private int depth;
        private Node[] subnodes = null;
        
        private Node[] Subnodes { 
            get {
                if ( subnodes == null ) {
                    subnodes = new Node[52]; // support A-Z a-z
                }
                return subnodes;
            }
        }
        
        public Node () : this(0) {}
        
        private Node ( int depth ) {
            this.depth = depth;
        }
        
        public int Add ( string str ) {
            Node current = this;
            for( int i=0; i<str.Length; i++ ) {
                int index = CharNodeIndex(str[i]);
                if ( current.Subnodes[index] == null ) {
                    current.Subnodes[index] = new Node( depth + 1 ); 
                }
                current = current.Subnodes[index];
            }
            current.count++;
            return current.count;
        }

        public int CountOf( string str ) {
            Node current = this;
            for( int i=0; i<str.Length; i++ ) {
                int index = CharNodeIndex(str[i]);
                if ( current.Subnodes[index] == null ) {
                    return 0; 
                }
                current = current.Subnodes[index];
            }
            return current.count;
        }

        private int CharNodeIndex ( char c ) {
            int index = 0;
            if ( c >= 'A' && c <= 'Z' ) {
                index = c - 'A';
            } else if ( c >= 'a' && c <= 'z' ) {
                index = c - 'a' + 26;
            } else {
                throw new ArgumentException("String may only contain the letters A-Z and a-z");
            }
            return index;
        }
        
    }
    
    static void Main(String[] args) {
        Node node = new Node();
        
        int strCount = int.Parse(Console.In.ReadLine());
        for ( int i=0; i<strCount; i++ ) {
            string str = Console.In.ReadLine();
            node.Add( str );
        }
        
        int queryCount = int.Parse(Console.In.ReadLine());
        for ( int i=0; i<queryCount; i++ ) {
            string str = Console.In.ReadLine();
            Console.Out.WriteLine( node.CountOf(str) );
        }
    }
}
    • nicholas_mahbou1 + 0 comments

      I used your solution to help me with my generic one but using LinkedLists instead of fixed size arrays

      using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        int numStrings = Int32.Parse(Console.ReadLine());

        var strings = new SparseArray<string, char>();

        for(int i = 0; i < numStrings; i++)
            strings.Add(Console.ReadLine());

        int numQueries = Int32.Parse(Console.ReadLine());

        for(int i = 0; i < numQueries; i++)
        {
            string query = Console.ReadLine();
            Console.WriteLine(strings.Count(query));
        }
    }
}

class SparseArrayNode<T>
{
    private T _item;
    private LinkedList<SparseArrayNode<T>> _list = new LinkedList<SparseArrayNode<T>>();

    public int Count { get; set; } = 0;

    public SparseArrayNode() { }

    public SparseArrayNode(T item)
    {
        _item = item;
    }

    public SparseArrayNode<T> AddChild(T item)
    {
        var sparseArrayNode = _list.AddLast(new SparseArrayNode<T>(item));
        return sparseArrayNode.Value;
    }

    public SparseArrayNode<T> Find(T item)
    {
        var currentNode = _list.First;

        while(currentNode != null)
        {
            if(currentNode.Value._item.Equals(item))
                return currentNode.Value;

            currentNode = currentNode.Next;
        }

        return null;
    }
}

class SparseArray<TCollection, TItem> where TCollection : IEnumerable<TItem>
{
    SparseArrayNode<TItem> _root = new SparseArrayNode<TItem>();

    public void Add(TCollection value)
    {
        var current = _root;

        foreach(var item in value)
        {
            var node = current.Find(item);

            if(node == null)
                node = current.AddChild(item);

            current = node;
        }

        current.Count++;
    }

    public SparseArrayNode<TItem> Find(TCollection value)
    {
        var current = _root;

        foreach(var item in value)
        {
            current = current.Find(item);

            if(current == null)
                break;
        }

        return current;
    }

    public int Count(TCollection value)
    {
        var node = Find(value);
        return node != null ? node.Count : 0;
    }
}
    • guangzefrio + 0 comments

      That You gived the solution solved my doubt on this problem.It's much better than using map directly as it used less memory.

    • putai + 0 comments

      Looks like a Trie implmentation to me. But again I am still trying to wrap my heads around Sparse Array and how to fit this problem into it.

    • azeyad + 0 comments

      I tried to find a way to implement a fix that somehow relates to the "Sparse Array" concept, but in sparse array we convert the array into a linked a list with the non empty entries only to save storage, so I imagined that converting the sparse array of word characters to a linked list is the way to go, here is my try:

      using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        int strCount = int.Parse(Console.In.ReadLine());
        for (int i = 0; i < strCount; i++)
        {
            string str = Console.In.ReadLine();
            AddWord(str);
        }
        int queryCount = int.Parse(Console.In.ReadLine());
        for (int i = 0; i < queryCount; i++)
        {
            string str = Console.In.ReadLine();
            actual_WordCount(str);
        }        
    }
    static WordNode StartWordNode = null;
    static WordNode LastWordNode = null;
    public static void AddWord(string word)
    {
        //Every new word add new word node             
        if (StartWordNode == null)
            LastWordNode = StartWordNode = new WordNode();
        else
            LastWordNode = LastWordNode.NextWordNode = new WordNode();
        CharacterNode currentCharacter = null;
        for (int i = 0; i < word.Length; i++)
        {
            if (currentCharacter == null)
                currentCharacter = LastWordNode.Character = new CharacterNode();
            else
                currentCharacter = currentCharacter.NextCharacterNode = new CharacterNode();
            currentCharacter.Char = word[i];
            currentCharacter.Position = i;
        }
    }    
    private static void actual_WordCount(string word)
        {
            int count = 0;
            WordNode currentWord = StartWordNode;
            while (currentWord != null)
            {
                CharacterNode currentCharNode = currentWord.Character;
                bool allCharsFound = true;
                for (int i = 0; i < word.Length; i++)
                {
                    if (currentCharNode.Char != word[i] || currentCharNode.Position != i || (i == word.Length - 1 && currentCharNode.NextCharacterNode != null))
                    {
                        allCharsFound = false;
                        break;
                    }
                    currentCharNode = currentCharNode.NextCharacterNode;
                }
                if (allCharsFound)
                    count++;
                currentWord = currentWord.NextWordNode;
            }
            Console.WriteLine(count);
        }
        public static void countWords()
        {
            int strCount = int.Parse(Console.In.ReadLine());
            for (int i = 0; i < strCount; i++)
            {
                string str = Console.In.ReadLine();
                AddWord(str);
            }
            int queryCount = int.Parse(Console.In.ReadLine());
            for (int i = 0; i < queryCount; i++)
            {
                string str = Console.In.ReadLine();
                actual_WordCount(str);
            }
        }    
    
}
public class CharacterNode
{
    public char Char { get; set; }
    public int Position { get; set; }
    public CharacterNode NextCharacterNode { get; set; }
}

public class WordNode
{
    public int WordCount { get; set; }
    public CharacterNode Character { get; set; }
    public WordNode NextWordNode { get; set; }
}
    • AD9000 + 0 comments

      Hi. I am new to sparse arrays so could you explain your code to me?

      As I see it, you are using a something like an array representation of a trie...is that correct? I particularly do not understand the use of the subnodes array properly.

      How are you storing the indices with the values or storing the total number of zeroes?